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;
}