欧拉函数

• 欧拉函数$\phi (n)$指$1$至$n$以内，与$n$互质的数的个数
• 假如n可以通过质因数分解得到质因子$p_1,p_2,p_3…p_n$
  • 则$\phi (n)=n(1-1/p_1)(1-1/p_2)(1-1/p_3)…(1-1/p_n)$
• 当n为质数时，$\phi (n)=n-1$

欧拉函数的性质

1. 当m与n互质时，$\phi (mn)=\phi (n)*\phi (m)$
2. 当n为质数时，$\phi (2n)=\phi (n)$

欧拉定理

• 若n与a互质，则$a^{\phi (n)}\equiv 1(mod n)$

• 利用该性质解决大数幂取模运算$a^x \mod n$,其中x与n互质

• 假设$x=m*(n-1)+t$
• 则$a^x \mod n=a^{n-1}a^{n-1}…a^{n-1}a^t \mod n$
• 因为$a^{\phi (n)}\equiv 1(mod n)$
• 所以$a^x \mod n=a^t \mod n$
• 即$a^x \mod n=a^{x \mod {n-1}}\mod n$

扩展欧拉定理

$$
a^x \mod n\equiv \begin{cases}
a^x,x<\phi (n) \\
a^{x\mod \phi (n)+\phi (n)}\mod n,x\geq \phi (n)
\end{cases}
$$

字符形式输入的大数取模处理方法

1
2
3
4
5
6
7
8

ll mod(){//求b%f(m)
	ll len=strlen(s),ans=0;
	for(int i=0;i<len;i++){
		ans=ans*10+(s[i]-'0');
		ans%=(m-1);
	}
	return ans;
}

return 0;

本文链接：
https://luojinrong.github.io/2019/05/15/欧拉定理/