浅谈数论

筛法与积性函数 欧拉筛

\(考虑每个数的最小质因数即可\)

$对于i\bmod prime[j] == 0 就break的解释 $

\(当 i是prime[j]的倍数时,i = k\times prime[j]\)

\(如果继续运算j+1,i\times prime[j+1] = prime[j] \times k\times prime[j+1]\)

\(这里prime[j]是最小的素因子,当i = k * prime[j+1]时会重复,所以才跳出循环\)

积性函数

\(\phi(n):欧拉函数,1-n中和n互质的数的个数\)

\(\mu(n):如果n的因式分解中有质因数的幂次大于1那么μ(n)=0,否则设n有k个质因数,μ(n)=(-1)^k\)

\(d(n):因数函数,n的正因数个数\)

\(σ(n):因数和函数,n的所有正因数之和\)

\(\phi相关\) \(普通求法 \Theta(sqrt(n))\)

\(考虑一个数n=\prod\limits_{i=1}^{cntp}p_i^{a_i},容斥即可\)

\(\phi(n)=n\times\prod\limits_{i=1}^{cntp}(1-\dfrac{1}{p_i})\)

\(或对单个整数N求欧拉函数φ(N)我们先将N进行因式分解对每个质因数的幂单独求φ再把他们乘起来\)

\(时间复杂度o(sqrt(N))\)

long long Phi(long long x) { long long res=x; long long now=x; for(long long i=2;i<=now/i;i++) { if(now%i==0) { res=res/i*(i-1); while(now%i==0) { now/=i; } } } if(now>1) { res=res/now*(now-1); } return res; } 筛法

\(积性函数,只要i\bmod prime[j] \not=0直接\phi(i*prime[j])=\phi(i)\times(prime[j]-1)\)

\(而i\bmod prime[j]=0,与i互质的与i*prime[j]同样互质,\phi(i*prime[j])=\phi(i)\times(prime[j])\)

拓展 \(\mathcal{No.1}\)

\(对于质数p,\phi(p^x)=p^x-p^{x-1}=(p-1)p^{x-1}\)

\(其实就是减去p的倍数\)

\(\mathcal{No.2}\)

\(对于1\le x\le m,使得其于n互质的个数\)

\(考虑容斥即可\)

\(\mathcal{No.3}\)

\(对于任意N>2,φ(N)是偶数\)

\(1-N中与N互质的数,可以两两配成和为N的数对。所以1-N中与N互质的数的和就是\dfrac{φ(N)*N}{2}\)

\(\mathcal{No.4}\)

\(\sum\limits_{d|n}\phi(d)=n\)

\(令f(n)=\sum\limits_{d|n}\phi(d),可证积性\)

\(对于质数p,f(p^k)=\sum\limits_{i=1}^{k}\phi(i)=\sum\limits_{i=1}^{k}(p^k-p^{k-1})=p^k\)

\(所以f(n)=\prod f(p^k)=\prod p^k=n\)

\(\mathcal{No.5}\)

\(\sum\limits_{i=1}^ngcd(i,n)=\sum\limits_{i=1}^n\sum\limits_{d|gcd(n,i)}\phi(d)=\sum\limits_{i=1}^n\sum\limits_{d|i}\sum\limits_{d|n}\phi(d)\)

\(\sum\limits_{d|n}\sum\limits_{i=1}^n\sum\limits_{d|i}\phi(d)=\sum\limits_{d|n}\dfrac{n}{d}\phi(d)\)

\(\mu相关\)

\(\sum\limits_{d|n}\mu(d)=[n=1]\)

d相关​

\(d(n)=\prod(1+a_i)\)

\(考虑每个因子互不影响\)

\(对于线性筛\)

\(维护每一个数的最小值因子出现的次数(即a1)即可\)

σ(n)相关

\(σ(i)=\prod\limits_{i=1}^k(\sum\limits_{j=1}^{a_i}p_i^{j})\)

欧拉定理 欧拉定理

\(对于互质的a,m,有a^{\phi(m)}\equiv1(\bmod m)\)

原根 阶

\(对于互质的两个正整数a和m,使得a^n ≡ 1 (\bmod m)成立的最小正整数n称为模m意义下a的阶\)

\(记作ord(a)。可以证明模m意义下的阶一定是φ(m)的因数\)

原根

\(对于互质的a,m,使得ord(a)=\phi(m),此时a是m的原根\)

\(a^0,a^1,...,a^{φ(m)-1}互不相同\)

\(如果a是m的一个原根,当且仅当GCD(b,φ(m))=1,a^b也是m的一个原根\)

\(当且仅当m=1、2、p^a或2*p^a时,m有原根\)

\(原根个数\phi(\phi(m))\)

威尔逊定理

\(当且仅当p是素数时,(p-1)! ≡ p-1 (mod\ p)\)

拓展欧拉定理

\(a^c\equiv a^{c\ mod\ \phi(m)+\phi(m)},c>=\phi(m)\)

\(a^c\equiv a^{c},c<\phi(m)\)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzzzyw.html