题目链接:
(SDIBT)
http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1499      
(FZU) 
http://acm.fzu.edu.cn/problem.php?pid=1759
题意描述:求A^B mod C,但是B的范围是1<=B<=10^1000000,是一个非常非常大的数。
题意分析:直接套用模板a^b%c是不行的。这个呢,有一个公式:a^b%c = a ^(b%eular(c)+eular(c)) % c,其中eular(c)是指c的欧拉函数,知道这个呢,用这个公式转化一下B,使B控制在long long范围内,就可以套用模板了。(注:SDIBT支持long long,FZU支持__int64)。这个题我感觉SDIBT比FZU的测试数据全。

代码如下:

#include<stdio.h>
#include<string.h>

char b[1000010];

long long Phi( int c ){

   long long ret = c;
   for(long long i=2; i*i<=c; i++){
       if( c % i == 0 )
           ret = ret / i * (i – 1 );
       while( c % i == 0 )
           c = c/i;
   }
   if( c > 1 )
       ret = ret / c * (c-1);
   return ret;
}

//这里有一点需要注意,在下面求积的地方要注意先求下余再乘,以防溢出,SDIBT在这上面有测试数据。
long long quick_mod(long long a,long long b,long long c){
   long long ret = 1, tmp=a%c;  
   while( b ){
       if( b & 1 )
           ret = (ret%c) * tmp % c ;
       tmp = tmp * tmp % c;
       b >>= 1;
   }
   return ret;
}

int main(){
   long long a,c,sum,bs,ec;
   while( scanf(“%lld%s%lld”,&a,b,&c) != EOF ){
       long long len = strlen(b);
       if( len < 11  ){
           bs=0;
           for(long long i=0; i<len; i++)
               bs = 10*bs + (long long)(b[i]-‘0’);
           sum = quick_mod( a,bs,c );
       }
       else{
           ec = Phi(c);
           bs=0;
           for(int i=0; i<len; i++)
               bs = (bs*10+(long long)(b[i]-‘0’) ) % ec;
           sum = quick_mod( a,bs+ec,c);
       }
       printf( “%lld\n”,sum );
   }
   return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation