给定正整数N, 求1≤x,y≤N且Gcd(x,y)为素数的数对(x,y)的对数. (1≤N≤10^7) 通常来讲, 枚举gcd是个不错的选择. 不妨先令x>y.
所以打一个素数表, 求欧拉函数函数前缀和-1即可 (扣除
说一下线性筛怎么打欧拉函数表. 首先, 对素数
最后把答案乘2加1.
#include <bits/stdc++.h>
#define Rep(i,a,b) for (int i=(a), i##_=(b); i<i##_; ++i)
#define For(i,a,b) for (int i=(a), i##_=(b); i<=i##_; ++i)
#define Down(i,a,b) for (int i=(a), i##_=(b); i>=i##_; --i)
using namespace std;
typedef long long ll;
const int MAX_N = 1e7;
int prime[MAX_N], phi[MAX_N + 1], cnt;
ll sum[MAX_N + 1];
void sieve(int n)
{
static bool f[MAX_N + 1];
phi[1] = 1;
For (i, 2, n) {
if (!f[i]) {
phi[i] = i-1;
prime[cnt++] = i;
}
for (int j = 0; j < cnt && i * prime[j] <= n; ++j) {
int k = i * prime[j];
f[k] = true;
if (i % prime[j] == 0) {
phi[k] = phi[i] * prime[j];
break;
} else
phi[k] = phi[i] * (prime[j]-1);
}
}
}
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n;
scanf("%d", &n);
sieve(n);
// 1<=j<i gcd(j, i)=1
For (i, 2, n) sum[i] = sum[i-1] + phi[i];
ll ans = 0;
Rep (i, 0, cnt)
ans += 2*sum[n/prime[i]] + 1;
printf("%lld\n", ans);
return 0;
}