AcWing 874. 筛法求欧拉函数

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

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

作者：

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

194

66

题目描述

给定一个正整数 $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)。

62 评论

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 的评论

# ~~%%%~~

藕丝泥霸 2024-01-21 20:23

or2

Gpd001 2024-02-02 17:59

# or2

半生落霜 2个月前

orz

350206A_u10551154ser30142325 19天前 ·福建回复了半生落霜的评论

#~orz~

350206A_u10551154ser30142325 19天前 ·福建回复了半生落霜的评论

# ~orz~

350206A_u10551154ser30142325 19天前 ·福建回复了 350206A_u10551154ser30142325 的评论

~~orz~~

Soel 2023-11-23 15:31

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

Soel 2023-11-23 15:32

快速幂+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 2023-11-23 15:32 回复了 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 2023-11-23 15:33 回复了 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;
}