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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4983 Goffi and GCD  

2014-08-25 18:48:05|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4983
题意:已知n和k,求满足条件的(a,b)有多少对
gcd(n-a, n)*gcd(n-b, n)=n^k
题解:
这题被自己的模板坑了,改了半天模板发现有个小bug,改好去交发现比赛刚刚结束,差了一分钟。。。
简单分析可以知道,如果k>2结果为0,k==2结果为1.
如果k==1,则看n的约数即可,求构成gcd(t,n)==i的t有多少个,i为n的约数。
上式变为求满足gcd(t,n/i)==1的t有多少个。
到这里,比赛的时候第一反应是用容斥原理求(因为之前遇到过类似的题),然后就套模板,之后发现模板有问题,然后就被坑了。。。赛后提交一发过了,看题解恍然大悟,这部分其实就是phi(n/i)(欧拉函数的定义)。
*注意:
gcd(0,n)=n;
如果n为1,结果为1.

LL n,k;

int tot,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 plen,p[N];
//分解质因子
void Getfac(LL n)
{
plen=0;
for(int i=0;prime[i]*prime[i] <= n ;i++)
{
if(n%prime[i] == 0)
{
p[plen++]=prime[i];
while(n%prime[i] == 0)
n/=prime[i];
}
if(n == 1)
break;
}
if(n > 1)
p[plen++]=n;
}

//容斥原理求解区间[1,n]内与m互质个数
LL dfs(int tmp,LL n)
{
LL s=0;
for(int i=tmp;i<plen;i++)
s=s+n/p[i]-dfs(i+1,n/p[i]);
return s;
}

//count num of gcd(n,i) == tmp
LL deal(LL tmp)
{
if(tmp == n)
return 1;
LL tag=n/tmp;
Getfac(tag);
return tag-dfs(0,tag);
}


LL fun1()
{
LL ans=0;
for(int i=1;i*i<=n;i++)
{
if(n%i == 0)
{
LL r1=deal(i);
LL r2=deal(n/i);
ans=(ans+(r1*r2)%MOD)%MOD;
if(i*i != n)
ans=(ans+(r1*r2)%MOD)%MOD;
}
}
return ans;
}

void solve()
{
if(n == 1)
{
pf(1);
return ;
}
if(k > 2)
{
pf(0);
return ;
}
if(k == 2)
{
pf(1);
return ;
}
pf64(fun1());
}

int main()
{
Getprime();
while(sf264(n,k)!=EOF)
solve();
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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