http://acm.fzu.edu.cn/problem.php?pid=1759
题意:
求A^B % C的值,A,C <= 1e9 , B<=10^1000000 ;
思路:
要解本题需要知道下面的公式:A^B = A^(B % phi(C) + phi(C) ) ( mod C ) , B>=phi(C) 。
有了上面的公式之后要解本题就简单了,先求出C的欧拉函数,然后比较B和phi(C)的大小,如果B>=phi(C) 直接用上面的公式二分求解,否则就暴力二分求解式子。
代码:
#include <stdio.h> #include <string.h> const int NN = 1000010 ; const int PP = 100010 ; typedef long long LL ; LL A , C ; char B[NN] , phi[20] ; LL prime[PP] ; int cnt ; bool is_p[PP] ; void calc(){ for(int i=1;i<PP;i++) is_p[i] = 1 ; cnt = 0 ; for(LL i=2;i<PP;i++){ if( is_p[i] ){ prime[ cnt ++ ] = i ; for(LL j=2 ; i*j<PP ;j ++ ){ is_p[ i*j ] = 0 ; } } } } LL get_phi( LL c ){ LL res = c ; for(int i=0;i<cnt && prime[i] * prime[i] <= c ; i++ ){ if( c % prime[i] == 0 ){ res = res / prime[i] *( prime[i] - 1 ) ; while( c%prime[i] == 0 ) c /= prime[i] ; } } if( c>1 ) res = res / c * (c - 1) ; return res ; } int check( LL ph ){ sprintf(phi ,"%lld" , ph) ; if( strlen(B) > strlen(phi) ) return 1 ; if( strlen(B) < strlen(phi) ) return 0 ; for(int i=0;i<strlen(B);i++){ if( B[i] > phi[i] ) return 1 ; else if( B[i] < phi[i] ) return 0 ; } return 1 ; } LL pow(LL a ,LL b , LL p){ LL res = 1 , add = a % p ; while( b ){ if( b&1 ) res = res * add % p ; add = add * add % p ; b >>= 1 ; } return res ; } LL deal(LL p){ LL res = 0 ; int len = strlen( B ) ; for(int i=0;i<len;i++){ res = ( res * 10 + B[i] - '0' ) % p ; } return res ; } int main(){ calc() ; while( scanf("%lld %s %lld",&A,B,&C) == 3){ LL ph = get_phi( C ) ; LL ans ; if( check(ph) ){ LL remain = deal( ph ) ; ans = pow(A , remain+ph , C) ; } else{ LL num; sscanf(B ,"%lld" ,&num ) ; ans = pow( A , num , C ) ; } printf("%lld\n",ans) ; } return 0 ; }