分析完题目，不就是要找y=kx有多少条0.0，那就是要找 (n-1)内gcd(i,j)==1的个数吗，最后答案+2就行了，直接走莫比乌斯反演。。。（题解区并没有人用）
最后特判n==1输出0就行了
#include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <algorithm> #include <iostream> using namespace std; #define ll long long #define re register const int N=4e4+10; const int M=4e4; inline void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } int mu[N],pri[N],cnt; bool vis[N]; inline void init() { mu[1]=1; for(re int i=2;i<=M;i++) { if(!vis[i]) pri[++cnt]=i,mu[i]=-1; for(re int j=1;j<=cnt&&i*pri[j]<=M;j++) { vis[i*pri[j]]=1; if(i%pri[j]==0) break; mu[i*pri[j]]=-mu[i]; } } for(re int i=1;i<=M;i++) mu[i]+=mu[i-1]; } inline ll solve(int n) { ll ans=0; for(int l=1,r;l<=n;l=r+1) { r=n/(n/l); ans+=(mu[r]-mu[l-1])*(n/l)*(n/l); } return ans; } int main() { init(); int n; read(n); if(n==1) return puts("0"),0; n--; printf("%lld",solve(n)+2); return 0; }