cf615D Multipliers
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).
Output
Print one integer — the product of all divisors of n modulo 109 + 7.
Example
2
2 3
36
3
2 3 2
1728
Note
In the first sample n = 2·3 = 6. The divisors of 6 are 1, 2, 3 and 6, their product is equal to 1·2·3·6 = 36.
In the second sample 2·3·2 = 12. The divisors of 12 are 1, 2, 3, 4, 6 and 12. 1·2·3·4·6·12 = 1728.
P是n个质数的乘积，问P的所有因子之积是多少
先把质数整理下，假设质数p[i]出现rep[i]次
P的所有因子个数应当是∏(rep[i]+1)，记为S
然后对于一个质数p[i]，出现0个，1个，...rep[i]个p[i]的因子个数都是S/(rep[i]+1)
因此p[i]对于答案的贡献就是j=0~rep[i]∏(p[i]^j)^(S/(rep[i]+1))
= p[i]^(rep[i]*(rep[i]+1)/2*S/(rep[i]+1))
=p[i]^(rep[i]*S/2)
此时rep[i]*S/2太大，可能爆long long,所以还要处理：
根据欧拉定理，有a^phi(p)==1(mod p)，所以p[i]^(1e9+6)==1(mod 1e9+7)
所以S*rep[i]/2可以对1e9+6取模
但是1e9+6不是质数，除二不好做，所以对它的两倍2e9+12取模，防止除2之后丢失信息
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define mkp(a,b) make_pair(a,b)
#define pi 3.1415926535897932384626433832795028841971
#define mod 1000000007
using namespace std;
inline LL read()
{
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
LL n,cnt;
LL a[];
LL p[],rep[];
LL ans=;
inline LL quickpow(LL a,LL b,LL MOD)
{
LL s=;
a%=MOD;
b=b%(MOD-);
while (b)
{
if (b&)s=(s*a)%MOD;
a=(a*a)%MOD;
b>>=;
}
return s;
}
int main()
{
n=read();for (int i=;i<=n;i++)a[i]=read();
sort(a+,a+n+);
for (int i=;i<=n;i++)
if (i==||a[i]!=a[i-])
{
p[++cnt]=a[i];
rep[cnt]=;
}else rep[cnt]++;
LL pro=;
for (int i=;i<=cnt;i++)pro=(pro*(rep[i]+))%(*mod-);
for (int i=;i<=cnt;i++)
{
ans=ans*quickpow(p[i],pro*rep[i]/%(*mod-),mod)%mod; }
printf("%lld\n",ans%mod);
}
cf615D
也可以不把S/(rep[i]+1)和rep[i]+1约掉，搞一个{rep[i]+1}的前缀积、后缀积，就可以绕过除法把rep[i]+1挖掉
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define mkp(a,b) make_pair(a,b)
#define pi 3.1415926535897932384626433832795028841971
#define mod 1000000007
using namespace std;
inline LL read()
{
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
LL n,cnt;
LL a[];
LL p[],rep[];
LL s[],t[];
LL phimod=;
LL mod2=;
LL ans=;
inline LL quickpow(LL a,LL b,LL MOD)
{
LL s=;
a%=MOD;
b=b%(MOD-);
while (b)
{
if (b&)s=(s*a)%MOD;
a=(a*a)%MOD;
b>>=;
}
return s;
}
int main()
{
n=read();for (int i=;i<=n;i++)a[i]=read();
sort(a+,a+n+);
for (int i=;i<=n;i++)
if (i==||a[i]!=a[i-])
{
p[++cnt]=a[i];
rep[cnt]=;
}else rep[cnt]++;
s[]=t[cnt+]=;
for (int i=;i<=cnt;i++)
{
s[i]=(s[i-]*(rep[i]+))%(mod-);
}
for (int i=cnt;i>=;i--)
t[i]=t[i+]*(rep[i]+)%(mod-);
for (int i=;i<=cnt;i++)
{
LL ap=s[i-]*t[i+]%(mod-);
ans=ans*quickpow(p[i],(rep[i]+)*rep[i]/%(mod-)*ap,mod)%mod;
}
printf("%lld\n",ans%mod);
}
cf615D_2
最新文章
- CoreCRM 开发实录——想用国货不容易
- Oracle数据加载之外部表的介绍
- iOS---初识Swift(一)
- Linux下如何修改ip地址
- LinkedHashMap实现LRU算法
- How to get the date N days ago in Python
- linux 常用命令及技巧
- Android之开源项目工具库篇
- 利用Java自带的MD5加密java.security.MessageDigest;
- py执行系统命令
- Android studio导出AAR包问题整理。
- docker结合jenkins、gitlab实现.netcore的持续集成实践
- C#windows服务调试技巧
- 【LeetCode】89.Gary Code
- python之string模块常量：数字，26个字母，标点符号，空白
- 读vue-0.6-filters.js源码
- link标签实现给网页标题前加一个小图标favicon.ico
- 分布式系统的Raft算法
- Cookis与文件缓存的区别
- Linux系统编程：文件I/O编程