今回謎の737推し。
http://community.topcoder.com/stat?c=problem_statement&pm=15075
問題
正整数a,b,c,mが与えられる。
a^(b^c) mod mを求めよ。
解法
b^cが十分小さい場合、具体的にはlog(m/a)以下の場合は愚直に計算してしまおう。
aを素因数分解し、各素因数a'に対しa'^(b^c) mod mを求めて掛け合わせることを考える。
よって、以下はaが素数である場合を考える。
問題はmが合成数の可能性があることである。
aとmが互いに素である場合、オイラーの公式よりである。
よってを答えればよい。
問題はaとmが素でない場合である。
m=a^x*y (yはaを約数に含まない正整数)とする。
1にaを(b^c)回掛け合わせることを考える。
最初のx回までは得られる値は単純にa^x % mとなる。
m / (a^x)はすでにaの倍数でない。よって上記オイラーの公式が成り立ち
となる。b^c-xが負になる可能性があるが、xは高々数十であり、b^cが小さい場合は別途処理済みなので気にしなくてよい。
class SimpleMathProblem { public: ll modpow(ll a, ll n,ll mo) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } int totient(int v) { int ret=v; for(int i=2;i*i<=v;i++) if(v%i==0) { ret=ret/i*(i-1); while(v%i==0) v/=i; } if(v>1) ret=ret/v*(v-1); return ret; } ll hoge(ll a,ll b,ll c,ll m) { int num=0; ll g=1; while(m%a==0) { m/=a; g*=a; num++; } if(m==1) return 0; if(m==2) return 1; int p=totient(m); ll t=modpow(b,c,p)+num*(p-1); return modpow(a,t,m)*g; } int calculate(int a, int b, int c, int m) { a %= m; if(m==1 || a==0) return 0; ll ret=1; if(log(b)*c<log(60)) { ll p=1; int i; FOR(i,c) p*=b; FOR(i,p) ret=ret*a%m; } else { for(int i=2;i*i<=a;i++) while(a%i==0) { ret=ret*hoge(i,b,c,m)%m; a/=i; } if(a>1) ret=ret*hoge(a,b,c,m)%m; } return ret; } }
まとめ
地味に手間取った。