原题链接
考察:快速幂
思路:
??简单题,但我\(wa\)了\(n\)次...
??\(mp\)统计\(sum-a[i]\)的出现次数.从小开始遍历,如果次数可以整除\(x\),则需要进位,注意每个地方都最好\(long long\)....
??还有就是分子可能＞分母,因为\(a\)最小可以 \(= 0\)
Code
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N = 100010,M = 1000000007;
int a[N],n,x;
LL sum,ans;
map<LL,LL> mp;
LL qsm(LL a,LL k,int m)
{
LL res = 1;
while(k)
{
if(k&1) res = (LL)res*a%m;
a = (LL)a*a%m;
k>>=1;
}
return res;
}
int main()
{
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=(LL)a[i];
for(int i=1;i<=n;i++)
mp[sum-a[i]]++;
while((*mp.begin()).second%x==0)
{
LL c = (*mp.begin()).first,d = (*mp.begin()).second;
while(d%x==0)
c++,d/=x;
mp.erase(mp.begin());
mp[c] += d;
}
ans = min((*mp.begin()).first,sum);
printf("%lld\n",qsm(x,ans,M));
return 0;
}