bzoj 2818 Gcd 【欧拉函数】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/44201813

问题：求 gcd(x,y)==质数, 1<=x,y<=n 的有多少对？

做这题的时候，懂得了一个非常重要的转化：求 (x, y) = k, 1 <= x, y <= n 的对数等于求 (x, y) = 1, 1 <= x, y <= n/k 的对数！所以，枚举每个质数 p， 然后求 (x, y) = 1, 1 <= x, y <= n/p 的个数。

(x, y) = 1 的个数如何求呢？欧拉函数！

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <queue>
#include <iterator>

using namespace std;

const int MAXN = 1000000;
int n;

int main()
{
	while (scanf("%d", &n) != EOF)
	{
		bool com[MAXN];
		int primes = 0, prime[MAXN], phi[MAXN];

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

		for (int i = 2; i <= n; i++)
			phi[i] = phi[i] + phi[i-1];
		long long ans = 0;

		for (int i = 0; i < primes; i++)
			ans += phi[n/prime[i]] * 2 -1;
		printf("%lld\n",ans);
	}
	return 0;
}