Prime Number CodeForces - 359C

原题链接
考察:快速幂
思路:
??简单题,但我\(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;
}

Prime Number CodeForces - 359C

原文：https://www.cnblogs.com/newblg/p/15116331.html