之前看了但是没有理解的莫比乌斯函数现在找题目练练手。。。
寒假里面看的当时理解不了就没有多管，导致现在写预处理函数很懵逼。。
题意：给定n,m,d,求出1<=x<=n,1<=y<=m中使得gcd(x,y)=d的x,y的对数
最简单的方法，O(n²)的暴力枚举就不用说了，但是这个数据范围肯定是过不了的。。
那么我们设函数f(d)为使得gcd(x,y)=d的x,y的对数
设函数F(d)为d可以整除gcd(x,y)的情况
那么显然有（仔细想一下或者手玩一下）
则
反演之后就是
那么我们先预处理μ的在范围内的值然后每次求一下F(d),那么就可以在根号时间内求出f(d)
代码：
在洛谷里面如果计算的那里不写成函数的话就过不了。。也不知道怎么回事就是TLE
//Decision's template #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; #define DP_maxn 16 #define maxn 100000 #define INF 10000007 #define mod 1000000007 #define mst(s,k) memset(s,k,sizeof(s)) typedef long long ll; struct Edge{ int from,to,dist; Edge(int u,int v,int d):from(u),to(v),dist(d){} }; /*---------------------------template End----------------------------*/ int n,a,b,d,ans,mu[maxn],vis[maxn],p[maxn],top = 0,x = 0,i,j; void mobius() { int N = 50000; mu[1]=1; for(i=2;i<=N;++i) { if(!vis[i]) { mu[i]=-1;p[++top]=i; } for(j=1;(n=i*(x=p[j]))<=N;j++) { vis[n]=1; if(i%x) mu[n]=mu[i]*mu[x]; else break; } } for(i=2;i<=N;++i) mu[i]+=mu[i-1]; } ll cal(int n,int m) { ll ans = 0; top = min(a,b); i = 1; for(i = 1;i<=top;i = j+1) { j = min(a/(a/i),b/(b/i)); ans += (ll)(mu[j]-mu[i-1])*(a/i)*(b/i); } return ans; } int main() { //ios::sync_with_stdio(false); //freopen("std.in","r",stdin); //freopen("std.out","w",stdout); mobius(); cin>>n; while(n--) { ans = 0; cin>>a>>b>>d; a/=d,b/=d; cout<<cal(a,b)<<endl; } return 0; }
