CodeForces - 359C Prime Number
题意：给一个素数和n个数，令s/t = 1/x^a1 + 1/x^a2 + 1/x^a3 + ......1/x^an,其中t = x^(a1+a2+a3+......an),求 s 与 t 的最大公因数，对 10^9+7取模
思路：分子分母都可以写为 m * ( x^k), m不能被x整除， 最大公因数就为x^k, k为分子分母较小的那一个，对于分母的k等于n个数的
和sum,分子为x^(sum-a1)+x^(sum-a2)+x^(sum-a3)+……+x^(sum-an),显然分子的k为（sum-an)的最小的那一个，但当数组a里的数有
重复的时候就不是这样了，
在第一组样例中会变成这样 2^2+2^2=2*2^2=2^3，那么这种情况下的k就为3而不是2了，
所以我们需要判断一下，假如将分子的次数k从小到大排序后，出现两个相同的k，那么就将这两项加到一块，让其系数加一，
如果前后两项并不相同，那么我们需要先判断一下它（次数k小的那一项）的系数m能否被素数x整除，如果能整除说明次数k可以增大（让其+1），并让m/=x
如果不能整除，那么这一项的k就是我们需要的分子的k了（k已经从小到大排过序，所以第一次找到的肯定就是答案）
最后对k快速幂
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define mod (1000000007);
ll a[100005];
ll q_pow(ll a,ll b){
ll r=1,base=a%mod;
while(b){
if(b&1) r=r*base%mod;
base=base*base%mod;
b>>=1;
}
return r;
}
int main(void)
{
ll n,x,sum=0;
scanf("%lld%lld",&n,&x);
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
for(int i=0;i<n;i++)
a[i]=sum-a[i];
sort(a,a+n);
ll ans,cnt=1;
a[n]=-1;
for(int i=1;i<=n;i++)
{
if(a[i]!=a[i-1])
{
if(cnt%x)
{
ans=a[i-1];
break;
}
else
{
cnt/=x;
a[i-1]+=1;
i--;
}
}
else cnt++;
}
ans=min(ans,sum);
printf("%lld\n",q_pow(x,ans));
return 0;
} 参考的
Alzh的博客
