AcWing 874. 筛法求欧拉函数

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 874. 筛法求欧拉函数原题链接简单

作者：

番茄酱 , 2019-08-22 17:17:44 , 所有人可见 , 阅读 13794

180

62

题目描述

给定一个正整数$n$，求$1$~$n$中每个数的欧拉函数之和。
数据范围：$1≤n≤10^6$

$1$~$N$中与$N$互质的数的个数被称为欧拉函数，记为$ϕ(N)$。
若在算数基本定理中，$N=p_1^{\alpha_1}p_2^{\alpha_2}···p_k^{\alpha_k}$，则：
$ϕ(N) = N∗\frac{p_1-1}{p_1}∗\frac{p_2-1}{p_2}∗…*\frac{p_k-1}{p_k}$

线性筛法同时求欧拉函数

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int primes[N], cnt;
int phi[N];
bool st[N];

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

int main()
{
    int n;
    cin >> n;

    get_eulers(n);

    LL res = 0;
    for (int i = 1; i <= n; i++) res += phi[i];
    printf("%lld\n", res);

    return 0;
}

代码解释：

质数$i$的欧拉函数即为phi[i] = i - 1：1 ~ $i-1$均与$i$互质，共$i-1$个。
phi[primes[j] * i]分为两种情况：
① i % primes[j] == 0时：primes[j]是i的最小质因子，也是primes[j] * i的最小质因子，因此1 - 1 / primes[j]这一项在phi[i]中计算过了，只需将基数$N$修正为primes[j]倍，最终结果为phi[i] * primes[j]。
② i % primes[j] != 0：primes[j]不是i的质因子，只是primes[j] * i的最小质因子，因此不仅需要将基数$N$修正为primes[j]倍，还需要补上1 - 1 / primes[j]这一项，因此最终结果phi[i] * (primes[j] - 1)。

51 评论

wqzgg 2023-02-03 16:09

# orz

wqzgg 2023-02-03 16:09

orz

wqzgg 2023-02-03 16:10

orz

wqzgg 2023-02-03 16:10

orz

wqzgg 2023-02-03 16:10

orz

wqzgg 2023-02-03 16:10

orz

ny_qinmuning 2023-08-06 18:45

# ~~orz~~

ny_qinmuning 2023-08-06 18:46 回复了 ny_qinmuning 的评论

# ~~tql~~

ny_qinmuning 2023-08-06 18:46 回复了 ny_qinmuning 的评论

# ~~%%%~~

藕丝泥霸 9个月前

or2

Gpd001 9个月前

# or2

一方神圣 2023-08-03 12:04

这题解，看着舒服

qiuqiu 9个月前

这里解释一下为什么i不能被p[j]整除的情况下，i与p[j]互质。

因为p[j]是质数，其约数只有1和自身，i不能整除p[j]，所以对于i和p[j]来说的最大公约数只有1，所以互质。

兜里没有钢镚 2023-05-10 19:34

# ORZZZZZZZZZZ

颓废 2023-03-14 12:11

orz

HHH6666666666 2022-10-17 19:09

%%%%%

wangxiulin 18天前

orz

想拉算法的手手 1个月前

tql orz

煦烊. 5个月前

zro 番茄 orz

佑佑变强日记 7个月前

为什么没有初始化cnt呢？

Soel 11个月前

考虑尝试快速幂+ml素性测试+fd+tho断环得到所有的因子，再直接套欧拉公式即可

Soel 11个月前

快速幂+ml素性测试

i64 gcd(i64 a, i64 b) { return b ? gcd(a, a % b) : a; }
i64 mul(i64 a, i64 b, i64 m) {
    return static_cast<__int128>(a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(i64 n) {
    if (n < 2)
        return false;
    static constexpr int A[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
    int s = __builtin_ctzll(n - 1);
    i64 d = (n - 1) >> s;
    for (auto a : A) {
        if (a == n)
            return true;
        i64 x = power(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool ok = false;
        for (int i = 0; i < s - 1; ++i) {
            x = mul(x, x, n);
            if (x == n - 1) {
                ok = true;
                break;
            }
        }
        if (!ok)
            return false;
    }
    return true;
}

Soel 11个月前回复了 Soel 的评论

fd+tho断环

std::vector<i64> factorize(i64 n) {
    std::vector<i64> p;
    std::function<void(i64)> f = [&](i64 n) {
        if (n <= 200000000) {
            for (int i = 2; i * i <= n; ++i)
                for (; n % i == 0; n /= i)
                    p.push_back(i);
            if (n > 1)
                p.push_back(n);
            return;
        }
        if (isprime(n)) {
            p.push_back(n);
            return;
        }
        auto g = [&](i64 x) {
            return (mul(x, x, n) + 1) % n;
            };
        i64 x0 = 2;
        while (true) {
            i64 x = x0;
            i64 y = x0;
            i64 d = 1;
            i64 power = 1, lam = 0;
            i64 v = 1;
            while (d == 1) {
                y = g(y);
                ++lam;
                v = mul(v, std::abs(x - y), n);
                if (lam % 127 == 0) {
                    d = gcd(v, n);
                    v = 1;
                }
                if (power == lam) {
                    x = y;
                    power *= 2;
                    lam = 0;
                    d = gcd(v, n);
                    v = 1;
                }
            }
            if (d != n) {
                f(d);
                f(n / d);
                return;
            }
            ++x0;
        }
        };
    f(n);
    std::sort(p.begin(), p.end());
    return p;
}

Soel 11个月前回复了 Soel 的评论

欧拉公式直接法

i64 phi(int x){
    auto t = factorize(x);
    t.erase(std::unique(t.begin(),t.end()),t.end());
    for(auto&pi:t){
        x = (x/pi)*(pi-1);
    }
    return x;
}