UVA10299 题解

sunyizhe · 2023-08-27 16:56:40 · 题解

这题是欧拉函数模板题，直接开整。

一、题面避雷

这题原题题面并不是求 \varphi(n)，而是说小于 n 且与 n 互质的数的个数。其实就是说求 \varphi(i)，但是当 i=1 时输出 0 即可。

二、\varphi(n) 的定义和求解

因为这题是模板题，所以有必要说明一下。

2.1 什么是 \varphi(n)

**特殊情况**：$n$ 是质数时，$\varphi(n)=n-1$。 ### 2.2 如何算出 $\varphi(n)

首先我们可以得知，当 \gcd(a,b)=1 时，\varphi(a \cdot b)=\varphi(a) \cdot \varphi(b)。可以称作欧拉函数是积性的。
插播：唯一分解定理：即任意一个大于 1 的整数均可分解质因数，且不管怎么分都只有一种质数组合。接下来计算 \varphi(n) 时要用到它。
插播：若 n=p^k（p 是质数），则 \varphi(n)=p_k-p_{k-1}。

我们可以来证一下：1 \sim n 每 p 个数分成一段，就有 1 \sim p，p+1 \sim 2p，\cdots，p_k-p+1 \sim p^k 这 p^{k-1} 段。每一段有 p-1 个数与 n 互质（因为每组都有 p^i，而 p^i \mid n），根据 \varphi(n) 的积性可知

由唯一分解定理，设 n=\prod_{i=1}^s {p_i}^{k_i}（p_i 是质数），有 \varphi(n)=n \times \prod_{i=1}^s \dfrac{p_i-1}{p_i}。

为什么呢？我们也可以来证明一下：

由唯一分解定理和 \varphi(n) 的积性与 2.1 所述特殊情况可知，

\begin{aligned} \varphi(n)&=\prod_{i=1}^s \varphi({p_i}^{k_i}) \\ &=\prod_{i=1}^s (p_i-1) \times {p_i}^{k_i-1} \\ &=\prod_{i=1}^s {p_i}^{k_i} \times (1-\frac{1}{p_i}) \\ &=n \times \prod_{i=1}^s (1-\frac{1}{p_i}) \\ &=n \times \prod_{i=1}^s (1-\frac{p_i-1}{p_i}) \end{aligned}

上述是当 n 只有一个质因子的情况。但由 \varphi(n) 的积性和唯一分解定理可以得到，只要将上述方法重复多次，就可对于任意一个正整数 n 算出 \varphi(n)。

2.3 程序实现

相信看到这里，程序也就差不多了。先初始化 ans=n，然后 for 枚举每个 n 的质因子 i。将 ans 赋值为 ans \div i \times (i-1)，然后将 n 的质因子 i 全部除去。最后得到 ans=\varphi(n)。

最后提醒一下别忘了第一章的坑。

三、代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int euler_phi(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }

    if(n>1)ans=ans/n*(n-1);//以防n是质数，上面的分解无法筛出来。若n是合数，则上面的分解完成后n应该是1
    return ans;
}
signed main()
{
    int n;
    while(cin>>n&&n)
    {
        if(n!=1)cout<<euler_phi(n)<<endl;//问这是为什么的，看第一章
        else cout<<0<<endl;
    }
    return 0;
}

四、鸣谢

本题解~~因为本人太蒻~~大部分证明都来自于 oi-wiki。

唯一分解定理超级简的介

欧拉函数非常详的解

想了解更多？（