Luogu2568 GCD

发布于 2019-09-17  169 次阅读


题目链接:Link

题意

给定整数N,求 1<=x,y<=NGcd(x,y) 为素数的数对 (x,y) 有多少对. (这个就是题面233333)

题解

很水的一道数论题

因为一个有序数对 (x,y)GCD 若要是一个质数,那么必然的,x, y 中必有一个是质数,否则不存在 GCD 是质数的可能(自行思考,很简单)。

那么对于每一个质数 p ,它的答案贡献就是 (1 ~ \frac{n}{p})

y 的取值范围进行讨论,当 y = x 时, 有且仅有 y = x = 1x | y

​ 当 y>x 时, 答案显然为\varphi (y)

最后的答案为所以有序互质对的个数为 (1 ~ \frac{n}{p}) 的欧拉函数之和乘2减1(要求的是有序互质对,因为有正反所以乘2以后减去(1, 1)多算的一次)

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int SIZE = 1e7 + 5;

int n, p, tot;
int phi[SIZE], prime[SIZE], vis[SIZE];
LL ans, sum[SIZE];

inline void Euler()
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i]) { phi[i] = i - 1; prime[++tot] = i; }
        for (int j = 1; j <= tot; j++)
        {
            int x = prime[j];
            if (i * x > n) break;
            vis[i * x] = 1;
            if (i % x == 0) { phi[i * x] = phi[i] * x; break; }
            else phi[i * x] = phi[i] * phi[x];
        }
    }
}

int main()
{
    scanf("%d", &n);
    Euler();
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + phi[i];
    for (int i = 1; i <= tot; i++)
        ans += sum[n / prime[i]] * 2 - 1;
    printf("%lld", ans);
    return 0;
}

朴实沉毅