数论总结

数论总结
欧拉筛

　　核心思想：对于每个合数，都用其最小质因子筛去，故复杂度O(n)

　　code：

　　关于这句话：

　　当prime[j]成为i的素因子时，那么i*prime[j]一定可以表现为一个更小的素因子和一个更大的合数的乘积，在后面一定会被筛去，因此这里直接关闭。

欧拉函数

　　怎样理解？

　　1.$p$为素数，那么结论显然成立。

　　2.1-p^a中，只有$p$的倍数可以被$p$整除，这样的倍数有p^a-1个，减去即可。

　　3.直接记下即可，证明如下：

　　对于第1行，与$m$互质的数有$φ(m)$个，而一共有$n$列，对于每个互质的数$r$，$k*m+r$与$m$也互质，故一共有$φ(m)$列数与$m$互质。又因为每一列的$n$个数$k*m+r$在$mod n$意义下构成一个完全剩余系（它们本身都不相等，$mod n$后余数都不相等），故$mod n$后的数构成的数列即为原数列的一个排列，故每一列都有$φ(n)$个数与$n$互质，故$φ(mn)=φ(m)*φ(n)$。