这样的点分成三类
1 不含0,要求三个数的最大公约数为1
2 含一个0,两个非零数互质
3 含两个0,这样的数只有三个,可以讨论
针对 1情况 定义f[n]为所有满足三个数最大公约数为n的三元组数量
F[n]为所有满足三个数的最大公约数能被n整除的三元组数量
显然 F[n]=∑n|df[d]
然后由莫比乌斯反演,f[n]=∑n|dμ[d/n]*F[d]
情况三也是一样的
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<iostream> #include<algorithm> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int N=1e6+5; int n,T,prime[N],mu[N]; bool vis[N]; void getmu() { mu[1] = 1; int cnt = 0; for(int i=2; i<=N-5; i++) { if(!vis[i]) { prime[cnt++] = i; mu[i] = -1; } for(int j=0; j<cnt&&i*prime[j]<=N-5; j++) { vis[i*prime[j]] = 1; if(i%prime[j]) mu[i*prime[j]] = -mu[i]; else { mu[i*prime[j]] = 0; break; } } } } LL F1(LL x){ x=n/x; return x*x*x; } LL F2(LL x){ x=n/x; return x*x*3; } int main(){ getmu(); scanf("%d",&T); while(T--){ scanf("%d",&n); LL ans=0; for(int i=1;i<=n;++i){ ans+=mu[i]*F1(i); ans+=mu[i]*F2(i); } printf("%lld ",ans+3); } return 0; }