注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 5525 Product  

2015-11-01 00:24:38|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=5525
BC#61。比赛时想得差不多,打了个TLE。结束后才想到了费马小定理处理……
给出一个序列A1 A2 …… An,得到hdu 5525 Product - fudq - fudqs AC Road。求N所有约数的积。
(1<=n<=105,0<=Ai<=105
题解:
首先可以将N整理成p1a1*p2a2……pkak的形式,其中pi是n的素因子。这部分只要打个素数表,然后素因子分解下就可以得到。
然后看每个素因子pi在所有约数里出现了多少次。不难发现,应该等于:
[(1 + ai) * a/ 2] * [(a+ 1) * (a2 + 1) * …… * (ai-1 + 1) * (ai+1 + 1) * …… * (a+ 1)]。
我们把上述式子前半部分里(1 + ai)移到后半部分里,变形为:
[(a/ 2)] * [(a+ 1) * (a2 + 1) *…… * (a+ 1)]。
那么我们可以先预处理出上述式子的后半部分,然后循环一遍所有素因子即可得到最后结果了。
这部分直接做,肯定超LL,这时我们可以用费马小定理处理,只需求出式子对(MOD - 1)取余即可。
需要注意个地方,在循环素因子累乘结果时,要注意前半部分式子里的除2操作。因为要对(MOD - 1)取余,(MOD - 2)不是素数,所以这里不能用乘法逆元。我们可以在求后半部分时,以及乘上ai进行特判,具体细节看代码。
这样就能求出每个素因子的次方数,再用快速幂取余,结果累乘下就好了。

int tot;
LL prime[N+10],f[N+10];
void Getprime()
{
memset(f,0,sizeof(f));
tot=0;
for(int i=2;i<=N;i++)
{
if(f[i] == 0)
prime[tot++]=f[i]=i;
for(int j=0;j<tot && prime[j]<=f[i] && i*prime[j]<=N;j++)
f[i*prime[j]]=prime[j];
}
}

int n,a[N+10];
LL p[N+10];

LL Mod_exp(LL a,LL b,LL c)
{
LL ans=1;
while(b)
{
if(b & 1)
ans=ans*a%c;
a=(a%c)*(a%c)%c;
b/=2;
}
return ans;
}

int main()
{
Getprime();
int n;
while(sf(n)!=EOF){
for(int i=1;i<=n;i++) sf(a[i]);
MEM(p);
for(int i=2;i<=n;i++) {
LL m=i;
for(int j=0;prime[j]*prime[j]<=m;j++){
while(m%prime[j] == 0){
p[j]+=a[i];
m/=prime[j];
}
}
if(m > 1){
int pos=lower_bound(prime,prime+tot,m)-prime;
p[pos]+=a[i];
}
}
LL res=1;
int flag=1;//需要对2特殊处理
for(int i=0;i<tot && prime[i] <= n;i++){
res=res*(p[i]+1);
if(res%2==0 && flag){
flag=0;
res/=2;
}
res=res%(MOD-1);//费马小定理处理
}
LL ans=1;
for(int i=0;i<tot && prime[i] <= n;i++){
LL tmp=res*p[i];
if(tmp%2==0 && flag) {
tmp/=2;//如果前面没有除2,需要在这里补充
}
tmp=tmp%(MOD-1);
ans=ans*Mod_exp(prime[i],tmp,MOD)%MOD;
}
pf64(ans);
}
return 0;
}


  评论这张
 
阅读(98)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017