[bzoj2818]Gcd

发表于   |  

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

Solution

预处理出n内的phi函数、质数。
然后枚举质数后累加phi。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#define maxn 10000000+1
typedef long long ll;
using namespace std;
int n, m, cnt;
bool vis[maxn];
ll phi[maxn], prime[maxn];
void getphi(int n){
	for (int i = 2; i <= n; i++){
		if (!vis[i]) {
			prime[++cnt] = i;
			phi[i] = i - 1;
		}
		for (int j = 1; j <= cnt, prime[j] * i <= n; j++){
			vis[prime[j] * i] = true;
			if (i % prime[j] == 0) {
				phi[prime[j] * i] = phi[i] * prime[j];
				break;
			}
			phi[prime[j] * i] = phi[i] * (prime[j] - 1);
		}
	}
	phi[1] = 0;
	for (int i = 2; i <= n; i++) phi[i] += phi[i-1];
}
ll sum = 0;
int main(){
	scanf(""%d"", &n);
	getphi(n);
	for (int i = 1; i <= cnt; i++){
		int x = n / prime[i];
		//cout<<x<<endl;
		sum += phi[x];
	}
	sum = 2 * sum + cnt;
	printf(""%lld"", sum);
}