题目
给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。
GCD(x,y)即求x，y的最大公约数。
输入格式 输入一个整数N
输出格式 输出一个整数，表示满足条件的数对数量。
数据范围 1≤N≤107 输入样例： 4 输出样例： 4
思路
题目要求x和y最大公约数是素数，转化gcd(x,y)为素数，设置p=gcd(x,y)，即有gcd(x/p,y/p)=1，即求N/p以内所有互质的数字的对数，用线性筛欧拉函数的方法求以下前缀和即可
代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std
;
typedef long long LL
;
const int N
= 1e7 + 10;
int primes
[N
], cnt
;
bool st
[N
];
int phi
[N
];
LL s
[N
];
void init(int n
)
{
for (int i
= 2; i
<= n
; i
++ )
{
if (!st
[i
])
{
primes
[cnt
++ ] = i
;
phi
[i
] = i
- 1;
}
for (int j
= 0; primes
[j
] * i
<= n
; j
++ )
{
st
[primes
[j
] * i
] = true;
if (i
% primes
[j
] == 0)
{
phi
[i
* primes
[j
]] = phi
[i
] * primes
[j
];
break;
}
phi
[i
* primes
[j
]] = phi
[i
] * (primes
[j
] - 1);
}
}
for (int i
= 1; i
<= n
; i
++ ) s
[i
] = s
[i
- 1] + phi
[i
];
}
int main()
{
int n
;
cin
>> n
;
init(n
);
LL res
= 0;
for (int i
= 0; i
< cnt
; i
++ )
{
int p
= primes
[i
];
res
+= s
[n
/ p
] * 2 + 1;
}
cout
<< res
<< endl
;
return 0;
}
