搜索
您的当前位置:首页正文

推导+欧拉函数,P2568 GCD

来源:步旅网

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接


二、解题报告

1、思路分析

gcd(x, y) = 素数p => x / p 和 y / p互质 => x ,y是 n / p内的互质的数对 => 想到欧拉函数

素数筛预处理欧拉函数和素数

对欧拉函数求前缀和

枚举质数p,其贡献为n / p内的互质对 * 2 - 1( - 1是因为1的互质数是1,对应数对为(p, p)要减去一个)

2、复杂度

时间复杂度: O(n)空间复杂度:O(n)

3、代码详解

#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e7;

int primes[N], cnt, n;
i64 phi[N];
std::bitset<N> isprime;

void init() {
    isprime[0] = isprime[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if (!isprime[i])
            primes[cnt ++] = i, phi[i] = i - 1;
        for (int j = 0; primes[j] <= n / i; j ++ ) {
            isprime[primes[j] * i] = 1;
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            if (i % primes[j] == 0) {
                phi[i * primes[j]] += phi[i];
                break;
            }
            
        }
    }
}


int main () {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n;
    init();
    i64 res = 0;
    for (int i = 1; i <= n; i ++ ) phi[i] += phi[i - 1];
    for (int i = 0; i < cnt; i ++) {
        res += (2LL * phi[n / primes[i]] - 1);
    }
    std::cout << res;
    return 0;
}

因篇幅问题不能全部显示,请点此查看更多更全内容

Top