#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 10000000
int pr,p[N+10],mu[N+10];
bool v[N+10];
int sum[N+10];
void init(){
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
//	时间复杂度O(n)
	for(int i=2;i<=N;i++){
		if(!v[i])p[++pr]=i,mu[i]=-1,v[i]=1,sum[i]=1;
		for(int j=1;j<=pr&&i*p[j]<=N;j++){
			v[i*p[j]]=1;
			if(i%p[j]==0){
				sum[i*p[j]]=mu[i];
				mu[i*p[j]]=0;
				break;
			}
			sum[i*p[j]]=-sum[i]+mu[i];
			mu[i*p[j]]=-mu[i];
		}
		sum[i]+=sum[i-1];
	}
/*	下面方法计算sum会慢300ms
	
	时间复杂度O(nlogn)
	for(int i=1;i<=pr;i++){
		for(int j=1;j*p[i]<=N;j++){
			sum[j*p[i]]+=mu[j];
		}
	}
	for(int i=1;i<=N;i++)sum[i]+=sum[i-1];*/
}
int calc(int n,int m){
	if(n>m)swap(n,m);
	int ans=0;
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		ans+=(sum[r]-sum[l-1])*(n/l)*(m/l);
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	init();
	int n;cin>>n;
	cout<<calc(n,n)<<'\n';
	
	return 0;
}

题目：求n以内满足gcd(i,j)=1的数对(i,j)的个数

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7;
int cnt, p[N+10];LL mu[N+10],F[N+10];bool v[N+10];
void init()
{
    cnt=0;mu[0]=0;mu[1]=1;memset(v, 0, sizeof(v));
    for(int i=2;i<=N;i++)
    {
        if(!v[i]) p[++cnt]=i; mu[i]=-1; 
        for(int j=1;j<=cnt&&p[j]*i<=N;j++)
        {
            v[i*p[j]]=true;
            if(i%p[j]==0) {mu[i*p[j]]=0; break;}
            mu[i*p[j]]=-mu[i];
        }
    }
    F[0]=0;
    for(int i=1;i<=cnt;i++)
        for(int j=p[i];j<=N;j+=p[i])
            F[j]+=mu[j/p[i]];
    for(int i=1;i<=N;i++)F[i]+=F[i-1];
}
LL calc(int n)
{
    LL ans=0;
    for(int l=1, r; l<=n; l=r+1)
    {
        r = n/(n/l);
        ans += (F[r] - F[l-1]) * (n/l) * (n/l);
    }
    return ans;
}
int main()
{
    init();
    int n;scanf("%d", &n);
    printf("%lld\n", calc(n));
    return 0;
}