给定整数N,求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。
GCD(x,y)即求x,y的最大公约数。
输入格式
输入一个整数N
输出格式
输出一个整数,表示满足条件的数对数量。
数据范围
1≤N≤10^7
输入样例:
4
输出样例:
4
思路:
代码:
#include <bits/stdc++.h>
const int N = 1e7 + 10;
#define ll long long
using namespace std;
int prime[N], cnt, phi[N], n;//prime[0]=2,cnt表示小于等于n有几个质数
bool st[N];
void Euler(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!st[i])
{
prime[cnt++] = i;
phi[i] = i - 1;
}
for (int j = 0; prime[j] <= n / i; j++)
{
int t = prime[j] * i;
st[t] = true;
if (i%prime[j] == 0)
{
phi[t] = phi[i] * prime[j];
break;
}
phi[t] = phi[i] * (prime[j] - 1);
}
}
}
ll sum[N];
int main()
{
int n;
cin >> n;
Euler(n);
sum[1] = 1;
ll res = 0;
for (int i = 2; i <= n; i++)sum[i] = sum[i - 1] + phi[i];
for (int i = 0; i < cnt; i++)
{
int now = n / prime[i];
res += 2 * sum[now] - 1;
}
cout << res << endl;
}