Codeforces 615D Multipliers (数论)

题目链接 Multipliers

题意很明确。

很显然答案可以表示成X ^ EXP % MOD

首先我们令N为输入的n个数的乘积。并且设N = (P1 ^ C1) * (P2 ^ C2) * ... * (Pk * Ck)，Pi(1 <= i <= k)为质数。

1、N为完全平方数。

这个时候X = N的算术平方根，EXP = (C1 +１) * (C2 + 1) * ... * (Ck + 1)， MOD = 1e9 + 7；

2、N不是完全平方数。

这个时候X = N， EXP = (C1 +１) * (C2 + 1) * ... * (Ck + 1) / 2， MOD = 1e9 + 7；

考虑到EXP可能非常大，这里我用了指数循环节公式：

　a^b%c = a^( b%phic+phic )%c　phix为欧拉函数。

而在题中c等于1e9 + 7为质数，那么phic = 1e9 + 6。

剩下的事情就很简单了。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define rep(i, a, b)  for(int i(a); i <= (b); ++i)
 6 #define LL            long long
 7 
 8 const int N     =    200010;
 9 const LL mod    =    1000000007;
10 
11 int prime[N];
12 int c[N], d[N];
13 bool fl;
14 int cnt = 0;
15 int n, x;
16 int squ;
17 
18 map <int, int> mp;
19 
20 
21 inline LL Pow(LL a, LL b, LL Mod){ 
22     LL ret(1); 
23     for (; b; b >>= 1, (a *= a) %= Mod) 
24         if (b & 1) (ret *= a) %= Mod; 
25     return ret;
26 }    
27 
28 
29 int main(){
30 
31     rep(i, 2, 200000){
32         fl = true;
33         rep(j, 2, (int)sqrt(i + 0.5)) if (i % j == 0){
34             fl = false;
35             break;
36         }
37         if (fl){
38             prime[++cnt] = i;
39             mp[prime[cnt]] = cnt;
40         }
41     }
42 
43     memset(c, 0, sizeof c);
44 
45     scanf("%d", &n);
46     rep(i, 1, n){
47         scanf("%d", &x);
48         ++c[mp[x]];
49     }
50 
51     squ = 1;
52     rep(i, 1, cnt)
53         if (c[i]){
54             if (c[i] & 1){
55                 squ = 0;
56                 break;
57             }
58         }
59         
60 
61     LL exp = 1;
62     if (squ){
63         LL ret = 1;
64         rep(i, 1, cnt) d[i] = c[i] / 2;
65         rep(i, 1, cnt) ++c[i];
66         rep(i, 1, cnt) (exp *= c[i]) %= (mod - 1);
67 
68         rep(i, 1, cnt) if (d[i]) (ret *= Pow(prime[i], d[i], mod)) %= mod;
69 
70         printf("%lld
", Pow(ret, exp + mod - 1, mod));    
71     }
72 
73     else
74     {
75         rep(i, 1, cnt) d[i] = c[i] + 1;
76         rep(i, 1, cnt) if (d[i] % 2 == 0){
77             d[i] >>= 1;
78             break;
79         }
80 
81         LL exp = 1;
82         rep(i, 1, cnt) (exp *= d[i]) %= (mod - 1);
83         LL ret = 1;
84         rep(i, 1, cnt) if (c[i]) (ret *= Pow(prime[i], c[i], mod)) %= mod;
85         
86         printf("%lld
", Pow(ret, exp + mod - 1, mod));
87     }
88     
89 
90     return 0;
91 
92 }