TopCoder SRM 660 Div2 Hard Powerit

妙に簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13802

問題

整数N,K,Mが与えられる。
を求めよ。

解法

とする。

各iに対し、f(i)を求めるのは繰り返し自乗法でO(K)で出来る。
ただ、愚直に毎回f(i)を計算するとO(NK)かかってしまうため、今回はNが10^6とそこそこ大きいのでこのままでは間にあわない。

そこで、iが合成数でi=p*qの時を考える。
そうするとf(i)=f(p)*f(q) mod Mなので、先にf(p),f(q)が求めてあればf(i)は簡単に求められる。
iが素数の時だけ愚直にf(i)を求めよう。

ll dp[1010000];
class Powerit {
	public:
	
	ll k21(int v,int k,int m) {
		ll ret=1, cur=v;
		while(k--) ret = ret*cur%m, cur = cur*cur%m;
		return ret%m;
		
	}
	int calc(int n, int k, int m) {
		ll ret=0;
		int i,j;
		ZERO(dp);
		for(i=1;i<=n;i++) {
			for(j=2;j*j<=i;j++) if(i%j==0) break;
			
			if(j*j<=i) dp[i]=dp[j]*dp[i/j]%m;
			else dp[i]=k21(i,k,m);
			
			ret += dp[i];
		}
		return ret%m;
	}
}

まとめ

これ900ptでいいんじゃないかなぁ…。