首页 > 代码库 > 快速幂

快速幂

2024-07-15 13:39:02   216人阅读

Raising Modulo Numbers http://poj.org/problem?id=1995

快速幂取模

 1 #include<cstdio> 2 typedef __int64 LL; 3 LL quickpow(LL a,LL b,LL c){//快速幂求(a^b)%c 4     LL ret=1%c; 5     for(;b;a=a*a%c,b>>=1){ 6         if(b&1){ 7             ret=ret*a%c; 8         } 9     }10     return ret;11 }12 int main(){13     int t,n;14     LL mod,a,b;15     while(~scanf("%d",&t)){16         while(t--){17             scanf("%I64d%d",&mod,&n);18             LL sum=0;19             while(n--){20                 scanf("%I64d%I64d",&a,&b);21                 sum+=quickpow(a,b,mod);22                 sum%=mod;23             }24             printf("%I64d\n",sum);25         }26     }27 }
View Code

 

Turn the pokers http://acm.hdu.edu.cn/showproblem.php?pid=4869

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef __int64 LL; 5 const int M=100010; 6 const int mod=1000000009; 7 LL quickpow(LL a,LL b,LL c){//快速幂求(a^b)%c 8     LL ret=1%c; 9     for(;b;a=a*a%c,b>>=1){10         if(b&1){11             ret=ret*a%c;12         }13     }14     return ret;15 }16 LL C[M];17 LL INV[M];18 int main() {19     for(int i=1; i<M; i++) {20         INV[i]=quickpow(i,mod-2,mod);21     }22     int n,m,a;23     while(~scanf("%d%d",&n,&m)) {24         C[0]=1;25         for(int i=1;i<=m;i++){26             C[i]=C[i-1]*(m-i+1)%mod*INV[i]%mod;27         }28         int L=0,R=0,nl,nr,tmp;29         for(int i=0;i<n;i++){30             scanf("%d",&a);31             tmp=min(m-L,a);32             nr=L+tmp-(a-tmp);33             tmp=min(R,a);34             nl=R-tmp+(a-tmp);35             if(nl>nr) swap(nl,nr);36             if(L<=a&&a<=R){37                 if(L%2==a%2){38                     nl=0;39                 }40                 else{41                     nl=min(nl,1);42                 }43             }44             if((m-R)<=a&&a<=(m-L)){45                 if((m-L)%2==a%2){46                     nr=m;47                 }48                 else{49                     nr=max(nr,m-1);50                 }51             }52             if(L>=a) nl=min(nl,L-a);53             if(m-R>=a) nr=max(nr,R+a);54             L=nl;55             R=nr;56         }57         int ans=0;58         for(int i=L;i<=R;i+=2){59             ans+=C[i];60             ans%=mod;61         }62         printf("%d\n",ans);63     }64     return 0;65 }
View Code

 

 

 

end


联系
我们