Dowemo
0 0 0 0

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 isAnd 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 theIt 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 = xIf 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