Dowemo

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





Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs