acwing练习
220. 最大公约数
给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。
GCD(x,y)即求x，y的最大公约数。
输入格式
输入一个整数N
输出格式
输出一个整数，表示满足条件的数对数量。
数据范围
1≤N≤1e7
输入样例：
4
输出样例：
4
这个目前也并没怎么看懂解析:https://www.cnblogs.com/gzh-red/p/11285929.html#_lab2_1_3
#include <bits/stdc++.h> const int maxn=1e7+10; using namespace std; #define int long long int phi[maxn],v[maxn],n,prime[maxn],m,sum[maxn],ans; void euler(){ m = 0; memset(v,0, sizeof(v)); for(int i = 2; i <= n; i++){ if(!v[i]) v[i] = 1,prime[++m] = i,phi[i] = i - 1; for(int j = 1; j <= m && i * prime[j] <= n; j++){ v[i * prime[j]] = 1; phi[i * prime[j]] = phi[i] *(i % prime[j] ? prime[j] - 1 : prime[j]); if(i % prime[j] == 0) break; } } } signed main(){ ios::sync_with_stdio(0); cin >> n; euler(); for(int i = 2; i <= n; i++) sum[i] = sum[i - 1] + phi[i]; for(int i = 1; i <= m; i++){ int now = n / prime[i]; ans += sum[now] * 2 + 1; } cout << ans; return 0; }
hfxcfsc