TopCoder SRM 737 Div2 Hard SimpleMathProblem

今回謎の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;
		
	}
}

まとめ

地味に手間取った。