Codeforces #238 Div2. D. Multipliers

CよりDの方が簡単…？
http://codeforces.com/contest/615/problem/D

問題

巨大な数の素因数分解の結果が与えられる。
この数の約数をすべて掛けた値を(10^9+7)で割った余りを求めよ。

解法

素因数分解した結果、i番目の素因数p[i]の次数がq[i]であったとする。
この巨大な数の約数のうち、p[i]の倍数でないものはx!=iにおける(q[x]+1)の積Q[i]である。
よって、巨大な数のうち素因数p[i]の次数が0,1,...,q[i]のものはQ[i]個ずつある。

そのため約数をすべて掛けた値を素因数分解するとp[i]の次数はq[i]*(q[i]+1)/2*Q[i]個ある。
フェルマーの小定理より、この値を(10^9+7)で割った余りを求めるには、p[i]を(q[i]*(q[i]+1)/2*Q[i])を(10^9+6)で割った余りの分累乗すればよい。

Q[i]の求め方は、(q[x]+1)の累積積を添え字の小さい順と大きい順両方求めておけば、(q[1]+1)～(q[i-1]+1)の累積積と(q[i+1]+1)～(q[n]+1)の累積積を掛けるだけで計算できる。

int N;
map<int,int> M;
ll mo=1000000007;
ll mo2=mo-1;
ll L[202020],R[202020];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		M[x]++;
	}
	vector<pair<int,int>> V;
	FORR(r,M) V.push_back(r);
	N=V.size();
	L[0]=R[N+1]=1;
	FOR(i,N) L[i+1]=L[i]*(V[i].second+1)%mo2;
	for(i=N;i>=1;i--) R[i]=R[i+1]*(V[i-1].second+1)%mo2;
	
	ll ret=1;
	FOR(i,N) {
		ll mul=1LL*V[i].second*(V[i].second+1)/2%mo2;
		(mul*=L[i]*R[i+2]%mo2)%=mo2;
		(ret*=modpow(V[i].first,mul))%=mo;
	}
	cout<<ret<<endl;
	
}

まとめ

これもう少し正答者少ないと思ったけど、意外と多かったな。