容斥原理与gcd的问题

gcd个数的处理(i,j无限制)

P2398 GCD SUM
i为1-n，j为1-m，求gcd为k的个数

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e5+5;

int f[M];

signed main() {
    int n;cin>>n;
    for(int i=n;i>=1;i--) {
        f[i]=(n/i)*(n/i);
        for(int j=i+i;j<=n;j+=i)f[i]-=f[j];
    }
    //左边多少个数，右边多少个数
    int ans=0;
    for(int i=1;i<=n;i++)ans+=i*f[i];
    cout<<ans<<endl;
    return 0;
}
//可以求出每一对gcd的数量

（i<j)

CF--841--E
gcd个数处理+贪心
其实也就是在上面的基础上除2的处理

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e6+5;

int a[M];

signed main() {
    int TT;cin>>TT;
    while(TT--) {
        int n,m,ans=0;
        cin>>n>>m;
        for(int i=n;i>=2;i--) {
            int k=i-1;//一次多少边
            a[i]=(n/i)*(n/i-1)/2;
            for(int j=2*i;j<=n;j+=i)a[i]-=a[j];
            int w=a[i]/k*k;//多少边
            if(w>m)w=m/k*k;
            m-=w;
            ans+=w/k*(k+1);
        }
        if(m>0)cout<<"-1\n";
        else cout<<ans<<endl;
    }
    return 0;
}
//适用容斥进行相减即可

1-n中与n互质的数的个数

可以适用欧拉，也可以适用容斥

欧拉

int phi(int x) {
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;//一次性消除全部i
        }
    if (x > 1) res = res / x * (x - 1);//有没有遗漏
    return res;
}

容斥

暂时不写，感觉没必要