懵逼乌斯反演//Hang in the air
首先以下断言成立!
1.ε(n)=∑d|nμ(d)
2.n=∑d|nφ(d)
第一类莫比乌斯反演
f(n)=Σd|ng(d) <=> g(d)=Σd|nμ(n/d)f(d)
第二类莫比乌斯反演
f(d)=Σd|ng(n) <=> g(d)=Σd|nf(n)μ(n/d)
要求满足gcd(i,j)=k(a<=i<=b且c<=j<=d)的有序数对(i,j)个数.
首先问题可以转化成求4个前缀和,然后求前缀和的时候可以再把形如:(n,m,k),表示满足gcd(i,j)=k(1<=i<=n且1<=j<=m)的有序对(i,j)个数.这样的询问转化成----问有多少对满足1<=i<=n/k且1<=j<=m/k的有序对(i,j)互质.
设f(x)=Σ(i=1..n)Σ(j=1..n)[gcd(i,j)==x],g(x)=Σx|if(i)
思考g(x)的实际意义----就是求所有的有序对(i,j)满足:1<=i<=n且1<=j<=m且x|i且x|j
∴g(x)=floor(n/x)floor(m/x)
∴f(x)=Σx|iμ(i/x)floor(n/i)floor(m/i)
然而问题是要求f(1)=Σμ(i)floor(n/i)floor(m/i)
这么求是O(n)的,已经很优啦,接下来把它优化要O(√n)
由于floor(n/i)一共有√n个结果,floor(m/i)一共有√m个结果,所以floor(n/i)*floor(m/i)最多有2*(√n+√m)个结果,预处理μ的前缀和,对于相同的结果直接加速...
Code:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define ll long long const int MAXN=50000; int t; int a,b,c,d,k; bool vis[MAXN+10]; int p[MAXN+10],tot; int moe[MAXN+10],premoe[MAXN+10]; void init() { for(int i=2;i<=MAXN;++i) { if(!vis[i]) { p[++tot]=i; moe[i]=-1; } for(int j=1;j<=tot&&(ll)p[j]*i<=MAXN;++j) { vis[p[j]*i]=true; if(i%p[j]==0){moe[p[j]*i]=0;break;} moe[p[j]*i]=-1*moe[i]; } } moe[1]=1; for(int i=1;i<=MAXN;++i)premoe[i]=premoe[i-1]+moe[i]; } ll work(int n,int m,int k) { ll res=0; n/=k;m/=k; for(int i=1,to,a,b;i<=n&&i<=m;i=to+1) { a=n/i;b=m/i; to=min(n/a,m/b); res+=(ll)(premoe[to]-premoe[i-1])*a*b; } return res; } int main() { init(); scanf("%d",&t); while(t--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); printf("%lld ",work(b,d,k)-work(a-1,d,k)-work(b,c-1,k)+work(a-1,c-1,k)); } return 0; }