传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=2818
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 9236 Solved: 4126
[Submit][Status][Discuss]
Description
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
HINT
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
解题思路：
老套路：GCD( x, y ) = p 转换成 GCD( x/p, y/p ) = 1；
那么按照原来的配方，我们需要枚举 x/p 或者 y/p 其中一个数，然后另外一个数的总数通过欧拉函数求得。
假设选择枚举 y/p ，那么还需要暴力一遍枚举素数。（一开始就是直接暴力。。。）
然而O( n ) 内可以同时筛出素数和欧拉函数值：https://oi.abcdabcd987.com/sieve-prime-in-linear-time/
同时记录一下欧拉函数前缀和 sum[k] ，根据上面的转换我们可知：
如果给出 x <= y ，则直接枚举素数枚举y，然后欧拉函数求所有方案数即可；
但是这里没有明确表明 x 和 y 的大小关系， 但是我们还是只求一半 即 （默认 x <= y)的情况，然后这个答案乘以 2 就是 （y <= x）的情况了，需要去一下重（即 x = y = 1)的情况。
枚举 素数 p ，求 [ 1, N/p ] 中互质的数对的总数， 即 2*sum[ N/p ] - 1;
AC code:
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 1e7+;
bool com[MAXN];
int primes, prime[MAXN], phi[MAXN];
LL sum[MAXN]; void get_phi(int n){
phi[] = ;
for (int i = ; i <= n; ++i)
{
if (!com[i])
{
prime[primes++] = i;
phi[i] = i-;
}
for (int j = ; j < primes && i*prime[j] <= n; ++j)
{
com[i*prime[j]] = true;
if (i % prime[j])
phi[i*prime[j]] = phi[i]*(prime[j]-);
else
{ phi[i*prime[j]] = phi[i]*prime[j]; break; }
}
//sum[i] = sum[i-1]+phi[i];
}
}
int main()
{
int N;
scanf("%d", &N);
get_phi(N);
sum[] = ;
for(int i = ; i <= N/; i++){
sum[i] = sum[i-]+phi[i];
// phi[i] = phi[i-1]+phi[i];
}
// printf("%d\n", phi[1]);
LL ans = ;
for(int i = ; i < primes; i++){
ans = ans + (sum[N/prime[i]]*-);
}
printf("%lld\n", ans); return ;
}