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。

剩下的事情就很简单了。

 #include <bits/stdc++.h>

 using namespace std;

 #define rep(i, a, b)  for(int i(a); i <= (b); ++i)

 #define LL            long long

 const int N     =    ;

 const LL mod    =    ;

 int prime[N];

 int c[N], d[N];

 bool fl;

 int cnt = ;

 int n, x;

 int squ;

 map <int, int> mp;

 inline LL Pow(LL a, LL b, LL Mod){

     LL ret();

     for (; b; b >>= , (a *= a) %= Mod)

         if (b & ) (ret *= a) %= Mod;

     return ret;

 }    

 int main(){

     rep(i, , ){

         fl = true;

         rep(j, , (int)sqrt(i + 0.5)) if (i % j == ){

             fl = false;

             break;

         }

         if (fl){

             prime[++cnt] = i;

             mp[prime[cnt]] = cnt;

         }

     }

     memset(c, , sizeof c);

     scanf("%d", &n);

     rep(i, , n){

         scanf("%d", &x);

         ++c[mp[x]];

     }

     squ = ;

     rep(i, , cnt)

         if (c[i]){

             if (c[i] & ){

                 squ = ;

                 break;

             }

         }

     LL exp = ;

     if (squ){

         LL ret = ;

         rep(i, , cnt) d[i] = c[i] / ;

         rep(i, , cnt) ++c[i];

         rep(i, , cnt) (exp *= c[i]) %= (mod - );

         rep(i, , cnt) if (d[i]) (ret *= Pow(prime[i], d[i], mod)) %= mod;

         printf("%lld\n", Pow(ret, exp + mod - , mod));

     }

     else

     {

         rep(i, , cnt) d[i] = c[i] + ;

         rep(i, , cnt) if (d[i] %  == ){

             d[i] >>= ;

             break;

         }

         LL exp = ;

         rep(i, , cnt) (exp *= d[i]) %= (mod - );

         LL ret = ;

         rep(i, , cnt) if (c[i]) (ret *= Pow(prime[i], c[i], mod)) %= mod;

         printf("%lld\n", Pow(ret, exp + mod - , mod));

     }

     return ;

 }