以下所有数，如果没有特殊说明，皆指正整数。
一些常识：
- \(\gcd(a+c\times b,b)=\gcd(a,b)\)。
- \(a\times b\equiv a\pmod c,\gcd(a,c)=1\Rightarrow b\equiv 1\pmod c\)
- \(a^b\equiv 1\pmod n\Rightarrow a^{b\times c}\equiv 1\pmod n\)。
1. 完全剩余系的定义
我们将 \(\{a_1,a_2,…a_n\}\)，其中 \(a_1,a_2,…,a_n\bmod n\) 互不同余，称为一个 \(\mod n\) 的完全剩余系。
2. 欧拉函数的定义以及性质
定义一个数 \(n\) 的欧拉函数 \(\varphi(n)\) 为 \([1,n]\) 中与 \(n\) 互质的整数个数。
首先，明显地，
- 如果 \(n\) 是质数，那么 \(\varphi(n)=n-1\)。
- 如果 \(n\) 是质数，那么 \(\varphi(n^k)=(n-1)\times n^{k-1}\)。这是因为由于 \(n^k\) 只含有质因数 \(n\)，所以 \([1,n^k]\) 里所有不与 \(n^k\) 互质的数只有所有 \(n\) 的倍数，一共 \(n^{k-1}\) 个数，所以 \([1,n^k]\) 中与 \(n^k\) 互质的数有 \((n-1)\times n^{k-1}\) 个。
定理 1：欧拉函数 \(\varphi\) 是一个积性函数，也就是如果 \(\gcd(a,b)=1\)，那么 \(\varphi(a\times b)=\varphi(a)\times\varphi(b)\)。
接下来我们要证明这件事。首先，我们知道，要与 \(a\times b\) 互质，就要同时与 \(a\) 和 \(b\) 互质。
引理 1：我们列出 \([1,a]\) 的所有与 \(a\) 互质的数：\(c_1,c_2,…,c_{\varphi(a)}\)。那我们知道在 \([1,a\times b]\) 里有且仅有 \(c_1,c_2,…,c_{\varphi(a)},c_1+a,c_2+a,…,c_{\varphi(a)}+a,c_1+2a,…,c_i+ja,…c_{\varphi(a)}+(b-1)a\) 这 \(b\times\varphi(a)\) 个数与 \(a\) 互质。
证明：
- \(\gcd(c_i+ja,a)=\gcd(c_i,a)=1\)。
- 如果存在 \(d\in[1,a\times b],d\ne\forall c_i+ja\) 并且 \(\gcd(d,a)=1\)，那么 \(d\bmod a\ne 0\)，假设 \(d=ae+f,0<f<a,f\ne \forall c_i\)，由于 \(\gcd(f+ea,a)=1\)，所以 \(\gcd(f,a)=1\)，与 \(c\) 中是 \([1,a]\) 的所有与 \(a\) 互质的数矛盾。
综上，引理 1 成立 □
引理 2：由于 \(\gcd(a,b)=1\)，所以 \(\forall i,c_i,c_i+a,c_i+2a,…,c_i+(b-1)a\bmod b\) 互不同余。
证明：如果存在 \(0\le j<k<b,c_i+ja,c_i+ka\) 使得 \(c_i+ja\equiv c_i+ka\pmod b\)，那么我们知道 \((k-j)a\equiv 0\pmod b\)，由于 \(\gcd(a,b)=1\)，所以 \(k-j\equiv 0\pmod b\)。由于 \(0<k-j<b\)，所以矛盾。
因此，引理 2 成立 □
那么结合引理 1、2，我们就可以知道在 \([1,a\times b]\) 里，只有 \(c_1,c_2,…,c_{\varphi(a)},c_1+a,c_2+a,…,c_{\varphi(a)}+a,c_1+2a,…,c_i+ja,…c_{\varphi(a)}+(b-1)a\)，其实就是 \(c_1,c_1+a,c_1+2a,…,c_1+(b-1)a,c_2,c_2+a,…c_2+(b-1)a,…,c_{\varphi(a)},c_{\varphi(a)}+a,…,c_{\varphi(a)}+(b-1)a\) 与 \(a\) 互质。那么其中 \(\forall i,c_i,c_i+a,c_i+2a,…,c_i+(b-1)a\mod b\) 互不同余，而且又刚好有 \(b\) 个，所以 \(\{c_i,c_i+a,c_i+2a,…,c_i+(b-1)a\}\) 与 \(\{1,2,…,b\}\) 一样，都是 \(\bmod b\) 的完全剩余系。由于 \(1,2,…,b\) 中恰有 \(\varphi(b)\) 个与 \(b\) 互质的数，所以 \([1,a\times b]\) 中恰有 \(\varphi(a)\times \varphi(b)\) 个与 \(a\times b\) 互质的数。
因此，定理 1 成立 □
定理 1 的推论：如果 \(n\) 不含质因数 \(p\)，那么 \(\gcd(n,p^k)=1\)，所以 \(\varphi(n\times p^k)=\varphi(n)\times\varphi(p^k)=\varphi(n)\times(p-1)\times p^{k-1}=\varphi(n)\times p^k\times\frac{p-1}{p}\)。
2. 欧拉函数求值方法
-
单独求值：我们可以得到任意正整数欧拉函数求值的方法：将 \(n\) 质因数分解，假设 \(n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times …\times p_k^{\alpha_k}\)，其中 \(p_i\) 是质数。那么它的欧拉函数 \(\varphi(n)\) 的值就是 \(n\times\prod\limits_{i=1}\limits^k\frac{p_i-1}{p_i}\)。时间复杂度 \(O(\sqrt n)\)。
-
如果我们要求 \(\varphi(1),\varphi(2),…,\varphi(n)\) 呢？我们可以利用欧拉函数是积性函数的性质，使用欧拉筛求解。时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll _=1000010;
ll c=0,p[_],e[_];
bitset<_>v;
int main(){
v.set();
for(ll i=2;i<_;i++){
if(v[i])p[++c]=i,e[i]=i-1;//i是质数,那么phi(i)=i-1
for(ll j=1;j<=c&&i*p[j]<_;j++){//正经筛法
v[i*p[j]]=0;
if(i%p[j])e[i*p[j]]=e[i]*(p[j]-1);//如果i*p[j]只有一个p[j],那要乘(p[j]-1)
else{e[i*p[j]]=e[i]*p[j];break;}//如果i*p[j]有多于一个p[j],那对于多出来的每个p[j],要乘p[j]
}
}
cout<<e[1000]<<'\n';//输出你需要的数
return 0;
}
3. 简化剩余系的定义
我们将 \(\{a_1,a_2,…,a_{\varphi(n)}\}\)，其中 \(a_1,a_2,…,a_{\varphi(n)}\bmod n\) 的结果与 \(n\) 互质，称为一个 \(\mod n\) 的简化剩余系。
4. 欧拉定理
定理 2：\(\gcd(a,n)=1\Rightarrow a^{\varphi(n)}\equiv 1\pmod n\)。
证明：假设 \(\{r_1,r_2,…,r_{\varphi(n)}\}\) 是一个 \(\mod n\) 的简化剩余系，那么使用类似引理 2 的证法，\(\{ar_1,ar_2,…,ar_{\varphi(n)}\}\) 也是一个 \(\mod n\) 的简化剩余系。所以 \(r_1\times r_2\times …\times r_{\varphi(n)}\equiv ar_1\times ar_2\times …\times ar_{\varphi(n)}\pmod n\)。因为 \(\gcd(r_1\times r_2\times …\times r_{\varphi(n)},n)=1\)，所以 \(a^{\varphi(n)}\equiv 1\pmod n\) □