积性函数

定义：若 $a,b$ 互质时，有 $f(ab)=f(a)*f(b)$ ,那么称函数 $f$ 为积性函数。

$ps$：$cbj$大佬说所有积性函数都可以用线性筛求值 $qwq$

欧拉函数

$\varphi(n)$ 表示比 $n$ 小的与 $n$ 互质的正整数的个数

对 $n$ 做质因数分解,得到 $n=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$ 则：

$$
\varphi(n)=n*(1-{1\over p_1})(1-{1\over p_2})\cdots *(1-{1\over p_m})
$$

证明：

若 $n$ 含有两个不同的质因子 $p,q$ ,

那么在 $1$ ~ $n$ 中 $p$ 的倍数有 $\cfrac {n}{p}$ 个，$q$ 的倍数有 $\cfrac {n}{q}$ 个，

如果我们把这 $\cfrac {n}{p}+\cfrac {n}{q}$ 个数减掉，

那么 $p,q$ 的共同因子就会被排除两遍，需要加回来一次。

因此 $1$ ~ $n$ 中不与 $n$ 含有共同因子 $p,q$ 的数的个数为：

$$
n-\cfrac {n}{p}-\cfrac {n}{q}+\cfrac {n}{pq}=n(1-{1\over p})(1-{1\over q})
$$

欧拉函数是积性函数

证明：根据我们得到的式子可得对于两个互质的数 $a,b$ 有

$$
\varphi(a)\varphi(b)=a*\prod_{质数p\mid a}(1-p)b\prod_{质数p\mid b}(1-p)=(ab)\prod_{质数p\mid (ab)}(1-p)=\varphi(ab)
$$

线性筛求欧拉函数的值 ：

需要利用的三条性质：

  • 1 若 $x$ 为质数，那么 $\varphi(x)=x-1$
  • 2 设 $p$ 为质数，若对于一个数 $x$ 有 $p\mid x$ 且 $p^2\mid x$ ,则 $\varphi(x)=\varphi(x/p)*p$
  • 3 设 $p$ 为质数，若对于一个数 $x$ 有 $p\mid x$ 但 $p^2\not\mid x$ ,则 $\varphi(x)=\varphi(x/p)*\varphi(p)$

证明：

第一条性质是显然的

第二条性质可以从公式中得到，因为 $x$ 和 $x/p$ 含有的质因子种类完全一样，所以 $\varphi(x)$ 和 $\varphi(x/p)$ 的商由公式可得是 $p$ ，所以 $\varphi(x)=\varphi(x/p)*p$

第三条性质可以直接由 $\varphi(n)$ 为积性函数得到

那么我们就可以利用这三条性质，在线性筛的基础上在 $\Theta(n)$ 的时间复杂度里求出 $1$~$n$ 的欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#define ll long long

ll n,phi[N],prime[N],tot,v[N];

for(int i=2;i<=n;i++){

    if(v[i]==0){

        prime[tot++]=i;

        phi[i]=i-1;

        v[i]=i;

    }

    for(int j=0;j<tot;j++){

        if(v[i]<prime[j]||prime[j]*i>n)break;

        v[i*prime[j]]=prime[j];

        if(i%prime[j])phi[i*prime[j]]=phi[i]*phi[prime[j]];

        else phi[i*prime[j]]=phi[i]*prime[j];

    }

}

欧拉定理

$$
a^{\varphi(n)}\equiv1\pmod n\quad\quad (a\bot n)
$$

证明：

$$
a^{\varphi(n)}x_1x_2x_3\cdots x_{\varphi(n)}\pmod n \tag{1}
$$

$$
\equiv (ax_1)(ax_2)\cdots(ax_{\varphi(n)})\pmod n \tag{2}
$$

因为 $a\bot n$ , 所以 $x_i\bot n$ ,所以 $ax_i\bot n$ ，所以 $ax_i \mod m$ 属于 $n$ 的简化剩余系，

因为 {$x_1,x_2,x_3\cdots x_{\varphi(n)}$} 正好构成了 $n$ 的简化剩余系，又有对于任意不相等的 $x_i,x_j$ 存在若 $a\bot n$ 那么 $ax_i\not\equiv ax_j\pmod n$

所以,对构成 $n$ 的简化剩余系的元素分别乘上 $a$ ,得到的数恰好又构成 $n$ 的简化剩余系,

即上面的式子等价于：

$$
x_1x_2x_3\cdots x_{\varphi(n)}\pmod n \tag{3}
$$

对(1)、(3)式两边同除 $x_1x_2x_3\cdots x_{\varphi(n)}$ 可得：

$$
a^{\varphi(n)}\equiv1\pmod n
$$

证毕。

可以发现其实费马小定理就是欧拉定理的特例，因为当p为质数时，$\varphi(p)=p-1$

扩展：

$$
a^{b}\equiv a^{b\mod\varphi(n)}\pmod n\quad\quad (a\bot n)
$$

证明：设 $b=q*\varphi(n)+r$ ,其中 $0\leq r<\varphi(n)$ ,即 $r=b \mod\varphi(n)$ ,于是：

$$
a^b\equiv a^{q*\varphi(n)+r}\equiv1^q*a^r\equiv a^r\equiv a^{b \mod\varphi(n)}\pmod n
$$

证毕

这个欧拉定理的小扩展可以帮我们有效降幂，但是他显然还不够一般，为了可以更方便的降幂，我们有：

扩展欧拉定理

$$
a^b \equiv a^{(b\mod\varphi(c))+\varphi(c)}\pmod c
$$

证明：

我们可以考虑对 $a$ 做质因数分解，

对于 $a$ 的质因数中与 $c$ 互质的 $p$ 因为欧拉定理显然符合上式，

对于 $p\mid c$ ，我们可以先把 $c$ 拆成 $sp^r$ ，其中 $s$ 与 $p$ 互质，因为$p^{\varphi(s)}\equiv 1\pmod s$，因为欧拉函数为积性函数，所以 $\varphi(s)\varphi(p^r)=\varphi(c)$ ，那么显然有

$$
p^{\varphi(c)}\equiv1\pmod s
$$

从而

$$
p^{b}\equiv p^{b\mod\varphi(c)}\pmod s
$$

两边同乘 $p^r$，因为 $c=s*p^r$，所以

$$
p^{b+r}\equiv p^{(b\mod\varphi(c))+r}\pmod c
$$

因为 $c=s*p^r$，所以 $\varphi(c)\ge r$，所以可以对两边同乘 $p^{\varphi(c)-r}$

$$
p^{b}\equiv p^{(b\mod\varphi(c))+\varphi(c)}\pmod c
$$

证毕