题目
给定一个正整数 $n$,求 $1 \sim n$ 中每个数的欧拉函数之和。
输入格式
共一行,包含一个整数 $n$。
输出格式
共一行,包含一个整数,表示 $1 \sim n$ 中每个数的欧拉函数之和。
数据范围
$1 \le n \le 10^6$
输入样例:
6
输出样例:
12
题解
思路
我们利用欧拉筛法找出1~n中所有数的欧拉函数,由于欧拉筛法是线性的,所有数只会被筛一次,我们就可以在这个过程中计算每个数的欧拉函数
先回忆欧拉函数公式
$$
ϕ(N) = N \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times … \times \frac{p_m-1}{p_m}
$$
我们将每个数i
分为三种
-
质数
-
i
是质数, 那i
的欧拉函数(也就是1~i
与i
互质的数) 有 i-1 个,因为i
是质数,所以除了它自身,1 ~ i-1所有数都与他互质 -
primes[j]
是当前数i
的质因子 -
那根据当前数
i
筛到的primes[j] * i
含有的质因子$p_1 … p_m$均与i
相同,原因是primes[j]
可以将i
整除,所以i
自身也含有primes[j]
这个质因子,那在primes[j] * i
的欧拉函数公式中$\frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times … \times \frac{p_m-1}{p_m}$均与i
的相同,公式中只有最前面的整数i
变为了primes[j] * i
,也就相当于在euler[i]
的基础上多乘一个primes[j]
c++ if (i % primes[j] == 0) //如果primes[j]是i的质因子 { euler[primes[j] * i] = euler[i] * primes[j]; break; //当遍历到的数i可以被当前质因子整除 break,保证某一个数都被他的最小质因子整除 }
-
primes[j]
不是当前数i
的质因子 -
那么数
primes[j] * i
就会在数i
的基础上多一个质因子primes[j]
,公式里相比euler[i]
前面多了primes[j]
,最后一项多了一个$\frac{primes[j]-1}{primes[j]}$ -
把这两项多的乘起来化简一下:$primes[j] * \frac{primes[j] - 1}{primes[j]} = primes[j] - 1$
c++ //如果primes[j]不是i的质因子 euler[primes[j] * i] = euler[i] * (primes[j] - 1);
自此我们就将三种情况考虑完了
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N]; //标记1~n中的合数
int euler[N]; //存储每一个数i对应的欧拉函数值
int res;
int n;
//利用欧拉筛模板求欧拉函数的和
void gets_primes(int n)
{
euler[1] = 1; //1的欧拉函数就是1
for (int i = 2; i <= n; i ++ )
{
if(!st[i]) //如果i是质数, 那i的欧拉函数(也就是1~i与i互质的数) 有i-1个,因为i是质数,所以除了它自身 1~i-1所有数都与他互质
{
primes[cnt ++ ] = i;
euler[i]= i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ ) //遍历所有质数,筛去i*primes[j]
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) //如果primes[j]是i的质因子
{
euler[primes[j] * i] = euler[i] * primes[j];
break; //当遍历到的数i可以被当前质因子整除 break,保证某一个数都被他的最小质因子整除
}
//如果primes[j]不是i的质因子
euler[primes[j] * i] = euler[i] * (primes[j] - 1);
}
}
}
void solve()
{
cin >> n;
gets_primes(n);
for (int i = 1; i <= n; i ++ ) res += euler[i]; //将1~n的欧拉函数加起来
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}