D. Multipliers
题目连接：
http://codeforces.com/contest/615/problem/D
Description
Ayrat has number n, represented as it's prime factorization pi of size m, i.e. n = p1·p2·...·pm. Ayrat got secret information that that the product of all divisors of n taken modulo 109 + 7 is the password to the secret data base. Now he wants to calculate this value.
Input
The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) — the number of primes in factorization of n.
The second line contains m primes numbers pi (2 ≤ pi ≤ 200 000).rst line of the input contains the string s — the coating that is present in the shop. Second line contains the string t — the coating Ayrat wants to obtain. Both strings are non-empty, consist of only small English letters and their length doesn't exceed 2100.
Output
Print one integer — the product of all divisors of n modulo 109 + 7.
Sample Input
2
2 3
Sample Output
36
Hint
题意
给你一个数的质因数，然后让你求出这个数所有因数的乘积
题解：
和hdu 5525很像，某场BC的原题
对于每个质因子，对答案的贡献为p^(d[p] * (d[p]-1) \ 2 * d[s])
d[p]表示p的因子数量，d[s]表示s这个数的因子数量
数量可以由因子数量定理求得,d[s] = (a1+1)(a2+1)...(an+1)，a1.a2.a3表示s的质因子的次数。
但是由于指数可能很大，所以我们就需要使用费马小定理就好了
但是又有除2的操作，mod-1有不是质数，不存在逆元，所以先对2（mod-1）取模。
代码
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
long long mod = 1e9+7;
long long mod2 = 2LL*(mod - 1);
long long quickpow(long long a,long long b,long long c)
{
long long ans = 1;
while(b)
{
if(b&1)ans = ans * a % c;
a = a * a % c;
b>>=1;
}
return ans;
}
int cnt[maxn];
int p[maxn];
int vis[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
cnt[p[i]]++;
}
long long tot = 1;
for(int i=1;i<=n;i++)
{
if(vis[p[i]])continue;
vis[p[i]]=1;
tot = tot*(cnt[p[i]]+1)%mod2;//求因子数
}
memset(vis,0,sizeof(vis));
long long ans = 1;
for(int i=1;i<=n;i++)
{
if(vis[p[i]])continue;
vis[p[i]]=1;
ans=ans*quickpow(p[i],(tot*cnt[p[i]]/2)%mod2,mod)%mod;//每个数的贡献，费马小定理
}
cout<<ans<<endl;
}