$HDU$1695 莫比乌斯反演
正解:莫比乌斯反演
解题报告:
这题是,莫比乌斯反演的板子,,,所以没什么好说的,只大概记录一下基操,具体学习笔记什么的,,,我大概以后会写$QAQ$?(,,,我最近越来越懒了鸽了好多学习笔记昂1551
首先因为是英文所以先翻译一个题意,,,大概就是,给定abcdk,然后求对于$x\in [a,b],y\in [c,d]$,有多少数对满足$gcd(x,y)=k$
然后保证$a$=$c$=1(,,,所以为什么要给定$a,c$昂,,,有猫病QAQ?
首先考虑到如果只是要求$gcd(x,y)$是$k$的倍数,就很好求嘛,就只要$xy$都是$k$的倍数就好,所以设$F(x)$表示$gcd$是$k$的倍数的数对数量,显然有$F(x)=⌊b/x⌋\cdot ⌊a/x⌋$
然后再设$f(x)$表示我们要的答案,也就是$gcd(x,y)=k$的数对数量,显然$F(x)=\sum f(d)$,其中$x|d$,这显然就转化成了莫比乌斯反演的性质?就是$f(x)=\mu (d/x)*F(d)$
然后这样还是有点儿不好做,所以可以考虑,再转化一下,显然gcd(x,y)=k能转化成gcd(x/k,y/k)=1
所以题目就变成了,求$f(1)$,其中要求$x\in [a,\frac{b}{k}],y\in [c,\frac{d}{k}]$
考虑关于$xy$的要求怎么转化?就显然是$F(d)$的那个$d=\frac{min(b,d)}{k}$就好
然后还没有做完,,,看题,说$(x,y)$和$(y,x)$是一样儿的
所以考虑去重,把重复的删去
然后就做完辣?
具体关于怎么求莫比乌斯函数以及这个$f(x)$的表达式之类的这篇博客里都不会有的,,,如果我有时间写莫比乌斯反演学习笔记的时候再说趴$QAQ$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
const int N=1e5+10;
int a,b,c,d,k,as1,as2,lim,miu[N],prim[N],pr_cnt;
bool isprim[N];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il void pre()
{
miu[1]=1;
rp(i,2,N-10)
{
if(!isprim[i])prim[++pr_cnt]=i,miu[i]=-1;
rp(j,1,pr_cnt)
{
if(prim[j]*i>N)break;
isprim[prim[j]*i]=1;if(!(i%prim[j]))miu[prim[j]*i]=0;else miu[prim[j]*i]-=miu[i];
}
}
}
main()
{
int T=read();pre();
// rp(i,1,20)printf("i=%lld miu=%lld\n",i,miu[i]);
rp(i,1,T)
{
printf("Case %lld: ",i);
a=read();b=read();c=read();d=read();k=read();as1=as2=0;
if(!k){printf("0\n");continue;}
b/=k;d/=k;lim=min(b,d);
rp(i,1,lim)as1+=1ll*miu[i]*(b/i)*(d/i);
rp(i,1,lim)as2+=1ll*miu[i]*(lim/i)*(lim/i);
printf("%lld\n",as1-as2/2);
}
return 0;
}