本文共 1700 字，大约阅读时间需要 5 分钟。
题意：给n，m，求出
思路：题意为求出1~m所有数和n的gcd之和。显然gcd为n的因数。我们都知道gcd（a，b）= c，那么gcd（a/c，b/c）= 1。也就是说我们枚举n所有的因数k，然后去找1~m/k中和n/k互质的个数就是gcd为k的个数。这个直接容斥就行。
代码：
#include #include #include #include #include #include #include #include #include #include using namespace std;#define inf 0x3f3f3f3f#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define mem(a,b) memset(a,b,sizeof(a));#define lowbit(x) x&-x;typedef long long ll;typedef unsigned long long ull;const double eps = 1e-6;const int maxn = 1e5+5;const ll mod = 1e8+7;ll prime[maxn], p[maxn], pn;void init(){ pn = 0; memset(prime, 0, sizeof(prime)); for(ll i = 2; i < maxn; i++){ if(!prime[i]){ p[pn++] = i; for(ll j = i * i; j < maxn; j += i) prime[j] = 1; } }}ll y[maxn], tot;ll solve(ll r, ll n){ //返回1~r和n的gcd为1个数 tot = 0; ll N = n; for(int i = 0; p[i] * p[i] <= N && i < pn; i++){ if(N % p[i] == 0){ y[tot++] = p[i]; while(N % p[i] == 0) N /= p[i]; } } if(N > 1) y[tot++] = N; ll num = 0; for(ll i = 1; i < (1 << tot); i++){ ll val = 1, times = 0; for(ll j = 0; j < tot; j++){ if((1 << j) & i){ times++; val *= y[j]; } } if(times & 1){ num += r / val; } else{ num -= r / val; } } return r - num;}int main(){ ll n, m, num, ans = 0, cnt = 0, temp; init(); scanf("%lld%lld", &n, &m); for(ll i = 2; i <= sqrt(n); i++){ if(n % i == 0){ num = solve(m / i, n / i); ans += num * i; cnt += num; if(i * i != n){ temp = n / i; num = solve(m / temp, n / temp); ans += num * temp; cnt += num; } } } num = solve(m / n, 1); ans += num * n; cnt += num; ans += m - cnt; printf("%lld\n", ans); return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/9888543.html
