Codeforces #209 Div2. C. Prime Number

CF209はDiv2 onlyで不参加。
どの問題もWAを重ねたけど、最終的には全部ノーヒントで解ききった。
http://codeforces.com/contest/359/problem/C

問題

素数Xと、数列P[i]が与えられる。
1/(X^P[0])+1/(X^P[1])+…+1/(X^P[N-1]) = s/tとおく。
ここでtは通分した(X^(P[0]+P[1]+…+P[N-1])とする場合、s/tを約分するために必要となる、sとtの最大公約数を求めよ。

解法

1/(X^P[0])を通分して分母をtにすると、分子はX^(P[1]+…+P[N-1])となる。
ここでB=P[0]+…+P[N-1]とすると、1/(X^P[i])=(X^(B-A[i])/tとなる。
後はX^(B-A[i])の総和を取り、Xの何乗を素因数に持つかを求め、分母であるt=X^Bの素因数の個数であるBとの小さい方を答えにすればよい。

ll mo=1000000007;
int N,X;
ll A[100001],XP[21];

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

void solve() {
	int f,i,j,k,l;
	ll x,y,N;
	
	cin>>N>>X;
	FOR(i,N) cin>>A[i];
	
	XP[0]=1;
	FOR(i,20) {
		if(XP[i]==-1) {
			XP[i+1]=-1;
		}
		else {
			XP[i+1]=XP[i]*X;
			if(XP[i+1]>N) XP[i+1]=-1;
		}
	}
	
	ll s=0;
	FOR(i,N) s+=A[i];
	FOR(i,N) A[i]=s-A[i];
	sort(A,A+N);
	y=A[0];
	FOR(i,N) A[i]-=y;
	x=0;
	FOR(i,N) if(A[i]<=20 && XP[A[i]]>=0) x+=XP[A[i]];
	while(x>0 && (x%X)==0) y++,x/=X;
	y=min(y,s);
	
	_P("%lld\n",modpow(X,y,mo));
}

まとめ

途中で何をはまったか、10回以上WAしてしまった…。