cfC.PrimeNumber

1 #include
2 #include
3 #include
4 #define maxn 200000
5 #define LL __int64
6 using namespace std;
7
8 LL a[maxn];
9 LL n,x;
10 LL min1(LL s,LL d)
11 {
12 if(s>d)return d;
13 return s;
14 }
15
16 LL pow_mod(LL a,LL p,LL m)//快速幂取模
17 {
18 if(p&＃61;&＃61;0) return 1;
19 LL ans1&＃61;pow_mod(a,p/2,m);
20 ans1&＃61;ans1*ans1%m;
21 if(p%2&＃61;&＃61;1) ans1&＃61;ans1*a%m;
22 return ans1;
23 }
24
25 int main()
26 {
27 while(scanf("%I64d%I64d",&n,&x)!&＃61;EOF)
28 {
29 LL sum&＃61;0;
30 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)
31 {
32 scanf("%I64d",&a[i]);
33 sum&＃43;&＃61;a[i];
34 }
35 LL ans&＃61;sum-a[n];//分子中最小公因子
36 LL c&＃61;a[n];
37 int t1&＃61;0;//记录可以产生1的个数
38 int pos&＃61;n;
39 while(c>&＃61;1)
40 {
41 while(a[pos]&＃61;&＃61;c&&pos>&＃61;1)
42 {
43 pos--;
44 t1&＃43;&＃43;;
45 }
46 c--;
47 if(t1%x&＃61;&＃61;0)
48 {
49 ans&＃43;&＃43;;
50 t1/&＃61;x;
51 }
52 else
53 break;
54 }
55 ans&＃61;min1(ans,sum);
56 printf("%I64d\n",pow_mod(x,ans,1000000007));
57 }
58 return 0;
59 }