[容斥][转化]求约数和

题目地址
题意很简单，就是求 $<mstyle displaystyle="true" scriptlevel="0"> <munderover> \sum i = 1 m </munderover> g c d (i, n) </mstyle>$ ,如果这道题m和n相等的话可以用欧拉函数搞定，问题是m和n不相等，所以要从别的角度考虑。
思路：因为n的约数个数很少，所以我们可以枚举n的约数，计算每个约数的贡献。
$<mstyle displaystyle="true" scriptlevel="0"> <munderover> \sum i = 1 m </munderover> g c d (i, n) </mstyle>$ = $<mstyle displaystyle="true" scriptlevel="0"> <munder> \sum d ∣ n </munder> d * <mstyle displaystyle="true" scriptlevel="0"> <munderover> \sum i = 1 \frac{m}{d} </munderover> [g c d (i, \frac{n}{d}) = = 1] </mstyle> </mstyle>$ 对于后面的式子，我们以用容斥搞一搞就行了。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+9;
int Case = 1;
ll query(ll n, ll m) {
	vector<ll>ve;
	for(ll i = 2; i*i <= n; i++) {
		if(n%i == 0) {
			ve.push_back(i);
			while(n%i == 0) n/=i;
		}
	}
	if(n>1) ve.push_back(n);
	ll t = ve.size();
	ll res = 0;
	for(ll i = 1; i < (1<<t); i++) {
		ll temp = 1, cnt = 0;
		for(ll j = 0; j < t; j++) {
			if(i&(1<<j)) {
				cnt++;
				temp *= ve[j];
			}
		}
		if(cnt&1) res += m/temp;
		else res -= m/temp;
	}
	return m-res;
}
ll n, m;
void solve() {
	vector<ll>ve;
	ll temp = n;
	for(ll i = 1; i*i <= temp; i++) {
		if(temp%i==0) {
			ve.push_back(i);
			if(i*i!=temp) ve.push_back(temp/i);
		}
	}
	ll res = 0;ll t = ve.size();
	for(ll i = 0; i < t; i++) {
		res += ve[i]*query(n/ve[i], m/ve[i]);
	}
	printf("%lld\n", res);
}

int main() {
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    //freopen("/Users/hannibal_lecter/Desktop/code/in.txt", "r", stdin);
    //freopen("/Users/hannibal_lecter/Desktop/code/out.txt","w",stdout);
#endif
    while(scanf("%lld%lld", &n, &m) == 2) {
        solve();
    }
    return 0;
}