首页 > 代码库 > HDU 1695 GCD（莫比乌斯反演）
HDU 1695 GCD（莫比乌斯反演）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=1695
【题目大意】
求出区间[1,b][1,d]中公约数为k的对数，重复的对数只计算一次。
【题解】
我们将b和d调整成b<=d，题目转化为[1,b/k][1,d/k]中互质的数对数，由于重复的对数只计算一次，因此需要再计算一次[1,b/k][1,b/k]，用原先答案减去计算出的一半就是答案。
【代码】
#include <cstdio>#include <algorithm>const int N=1000010;using namespace std;typedef long long ll;int T,a,b,c,d,k;int tot,p[N],miu[N],sum[N],v[N];void mobius(int n){ int i,j; for(miu[1]=1,i=2;i<=n;i++){ if(!v[i])p[tot++]=i,miu[i]=-1; for(j=0;j<tot&&i*p[j]<=n;j++){ v[i*p[j]]=1; if(i%p[j])miu[i*p[j]]=-miu[i];else break; } }for(i=1;i<n;i++)sum[i]=sum[i-1]+miu[i];}ll cal(int n,int m){ ll t=0; if(n>m)swap(n,m); for(int i=1,j=0;i<=n;i=j+1)j=min(n/(n/i),m/(m/i)),t+=(ll)(sum[j]-sum[i-1])*(n/i)*(m/i); return t;}int Cas;int main(){ mobius(1000000); scanf("%d",&T); while(T--){ scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); if(b>d)swap(b,d); if(k==0)printf("Case %d: 0\n",++Cas); else printf("Case %d: %lld\n",++Cas,cal(b/k,d/k)-cal(b/k,b/k)/2); }return 0;}
HDU 1695 GCD（莫比乌斯反演）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。