# CodeForces

Codeforces - 359C prime number for a number and number of n, s t = 1/x^a1 + 1/x^a2 + 1/x^a3 +. 1/x^an, where t = x^ ( a1 + a2 + a3 +. An ), find the maximum common factor for s and t, where t = ( a1 + a3 + a3 +. ). Thought: the molecular denominator can be written to m * ( x^k ), and m can't be divided by x, and the maximum common factor is x k, k is the one whose numerator is And sum, the molecule is x ( sum-a1 ) + x^ ( sum-a2 ) + x^ ( sum-a3 ) + ( ) + x^ ( sum-an ), apparently the smallest molecule 's k ( sum-an ), but when the number in array a has the It isn't that when you repeat it. In the first set of samples, 2^2 + 2^2 = 2 * 2^2 = 2^3, so k is 3 rather than 2.
So we need to judge that if the number of times k of the molecule is ordered, two of the same k will appear, then the two are added to a block to increase the coefficient
If the first two aren't equal, then we need to determine if the coefficient m of the small number of k is divided by prime x, if it can be evenly divided ( let + 1 ), and let m = x If you can't divide it, then the k of this one is the k of the molecule we need ( k has been sorted out of order, so the first one will be the answer ).
Finally, the k power

#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("%lldn",q_pow(x,ans));

return 0;

}




A blog for alzh