本文共 1917 字，大约阅读时间需要 6 分钟。

题目链接:

题目描述

给定一个正整数n，求1~n中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示1~n中每个数的欧拉函数之和。

数据范围

1≤n≤10^6

输入样例

6

输出样例

12

解题思路

题意:求1~n中每个数的欧拉函数之和。

要想求欧拉函数需要用到以下几个性质(p为质数):

证明:

• 因为质数p除了1以外的因子只有p，所以与p互素的个数是p-1个。
• 令,小于n的正整数共有个,其中与p不互质的个数共个，它们是，所以。

• 如果i mod p = 0, 那么 phi(i * p) = p * phi(i) (证明略，其实不会证...)
• 如果i mod p != 0, 那么 phi(i * p) = phi(i) * (p-1)

证明:

• i mod p 不为0且p为质数, 所以i与p互质,那么根据积性函数的性质 phi(i * p) = phi(i) * phi(p)，其中phi(p) = p-1，所以 phi(i * p) = phi(i) * (p-1).

根据这些性质，我们就可以写代码了。

Accepted Code:

//埃筛/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;const int MAXN = 1e6 + 5;int phi[MAXN];void Euler(int n) {    for (int i = 0; i <= n; i++)        phi[i] = i;    for (int i = 2; i <= n; i++) {        if (!(phi[i] != i)) {            for (int j = i; j <= n; j += i)                phi[j] = phi[j] / i * (i - 1);        }    }}int main() {    int n;    scanf("%d", &n);    Euler(n);    long long ans = 0;    for (int i = 1; i <= n; i++)        ans += phi[i];    printf("%lld\n", ans);    return 0;}
   

//线性筛/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;const int MAXN = 1e6 + 5;bool vis[MAXN];int prime[MAXN], phi[MAXN];void Euler(int n) {    phi[1] = 1;    int cnt = 0;    for (int i = 2; i <= n; i++) {        if (!vis[i]) {            prime[cnt++] = i;            phi[i] = i - 1;        }        for (int j = 0; j < cnt && prime[j] <= n / i; j++) {            vis[prime[j] * i] = true;            if (i % prime[j])                phi[i * prime[j]] = phi[i] * (prime[j] - 1);            else {                phi[i * prime[j]] = phi[i] * prime[j];                break;            }        }    }}int main() {    int n;    scanf("%d", &n);    Euler(n);    long long ans = 0;    for (int i = 1; i <= n; i++)        ans += phi[i];    printf("%lld\n", ans);    return 0;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/99691777 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！