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してしまった…。