BZOJ 2818 Gcd 线性欧拉筛（Eratosthenes筛）

题目大意：给定整数N(N <= 1e7)，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.、

思路：推一推。

设gcd(x,y) = p,则x / p与y / p互质

问题就转化成了N / p中有多少个数互质,然后累加就可以了.

=>对于任意a,b,a <= N / p,b <= N / p,且a与b互质

=>gcd(a,b) == 1

现在问题就很明显了，看到这个形式就很容易想到欧拉函数，求一下phi，算一下前缀和，累加。

注意这里求欧拉一定要线性的，1qw的数据，nloglogn都很悬。

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 10000010
using namespace std;

bool not_prime[MAX];
int prime[MAX],primes;
long long phi[MAX],ans;

int n;

inline void Eratosthenes();

int main()
{
	cin >> n;
	Eratosthenes();
	for(int i = 2;i <= n; ++i)
		phi[i] += phi[i - 1];
	for(int i = 1;i <= primes; ++i)
		ans += phi[n / prime[i]];
	cout << (ans << 1) - primes << endl;
	return 0;
}

inline void Eratosthenes()
{
	phi[1] = 1;
	for(int i = 2;i <= n; ++i) {
		if(!not_prime[i])
			prime[++primes] = i,phi[i] = i - 1;
		for(int j = 1;j <= primes && prime[j] * i <= n; ++j) {
			not_prime[i * prime[j]] = true;
			if(i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else	phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
}

BZOJ 2818 Gcd 线性欧拉筛（Eratosthenes筛）

原文：http://blog.csdn.net/jiangyuze831/article/details/39890503