[复习] 数论基础
模运算
\[(a\pm b)\bmod p=((a\bmod p)\pm(b\bmod p))\bmod p \]\[(a\times b)\bmod p=((a\bmod p)\times(b\bmod p))\bmod p \]积性函数
\[\forall\gcd(x,y)=1,f(xy)=f(x)\times f(y) \]完全积性函数
\[\forall x,y\in N^+,f(xy)=f(x)\times f(y) \]gcd
由欧几里得定理
\(\gcd(a,0)=a,\gcd(a,b)=\gcd(b,a\bmod b)\)。
exgcd
用于求解 \(ax+by=\gcd(a,b)\) 的解。
如果 \(x_0,y_0\) 是 \(bx+(a\bmod b)\times y=\gcd(b,a\bmod b)\) 的解。
那么 \(x=y_0,y=x_0-\lfloor\frac a b\rfloor \times y_0\) 是 \(ax+by=\gcd(a,b)\) 的解。
int exgcd(int a,int b,int &x,int y){
if(b==0) { x=1,y=0; return a; }
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
线性同余方程
求解 \(ax\equiv b\pmod m\)。
那么 \(ax+km=b\)。
就变成了求解线性不定方程。
线性不定方程
求解 \(ax+by=c\)。
如果 \(\gcd(a,b)\nmid c\)，那么方程无解。
否则我们可以求解 \(ax+by=\gcd(a,b)\)，的解 \(x_0,b_0\)。
那么 \(ax+by=c\) 的其中一组整数解就是 \(x_1=x_0\times \frac{c}{\gcd(a,b)},y_1=y_0\times \frac{c}{\gcd(a,b)}\)。
而任意解可以表示为 \(x=x_1+k\times\frac{b}{\gcd(a,b)},y=y_1-k\times \frac a {\gcd(a,b)}\)。
（扩展）中国剩余定理
\[x\equiv a_1\pmod {m_1} \]\[x\equiv a_2\pmod {m_2} \]那么有 \(x=k_1m_1+a_1=k_2m_2+a_2\)。
\[k_1m_1-k_2m_2=a_2-a_1 \]用 \(exgcd\) 求解，若无解则说明同余方程组无解。
然后两个同余方程化为一个同余方程
\[x\equiv k_1m_1+a_1\pmod {lcm(m_1,m_2)} \]欧拉函数
\[\varphi(n)=\sum_{i=1}^n[\gcd(n,i)=1] \]\[\sum_{i\mid n}\varphi(n)=n \]\[n=\prod_{i=1}^kp_i^{c_i}(p_i\in prime,p_i\ne p_j)\Rightarrow\varphi(n)=n\times\prod_{i=1}^k\dfrac {p_i-1} {p_i} \]\[\forall \gcd(i,j)=1,\varphi(ij)=\varphi(i)\times\varphi(j) \]（扩展）欧拉定理
\[\forall \gcd(a,p)=1,a^b\equiv a^{b\bmod \varphi(p)}\pmod p \]\[a^b\equiv a^{(b\bmod \varphi(p))+\varphi(p)}\pmod p \]费马小定理
由欧拉定理，当 \(p\) 为质数时
\[a^p\equiv a \pmod p \]\[a^{p-1}\equiv 1\pmod p \]\[a^{p-2}\equiv a^{-1}\pmod p \]乘法逆元
当 \(\gcd(a,m)=1\) 时，定义 \(a\) 的乘法逆元 \(a^{-1}\) 为
\[ax\equiv 1\pmod m \]的解。
方法一
当 \(m\) 为质数时，由费马小定理，\(a^{p-2}\equiv a^{-1}\pmod m\)。
方法二
用 \(exgcd\) 求解 \(ax+mk=1\) 这个不定方程。
当且仅当 \(\gcd(a,m)=1\) 时有解。
Lucas定理
\[\binom n m\bmod p=\binom {\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\times \binom {n\bmod p}{m\bmod p}\bmod p \]整除分块（数论分块）
我们有
\[\dfrac{\lfloor\frac{x}{y}\rfloor}{z}=\lfloor \dfrac{x}{yz}\rfloor \]求
\[\sum_{i=1}^n\lfloor\frac ni\rfloor \]结论 \(x=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\) 是最大的满足 \(\lfloor\frac{n}{x}\rfloor=\lfloor\frac{n}{i}\rfloor\) 的 \(x\)。
狄利克雷卷积
定义 \(f(x)\) 和 \(g(x)\) 狄利克雷卷积 \(h=f*g\) 为
\[h(x)=\sum_{d\mid x} f(d)g(\frac{x}{d})=\sum_{ab=x}f(a)g(b) \]狄利克雷卷积有交换律、结合律、分配律。
几个基础数论函数
\[I(n)=1 \]\[id(n)=n \]\[\varepsilon(n)=[n=1] \]\[d(n)=\sum_{i\mid n} 1 \]\[\sigma(n)=\sum_{i\mid n}i \]其中 \(\varepsilon\) 是单位元，对于任意函数 \(f\) 都有 \(f*\varepsilon =f\)。
如果 $f*g=\varepsilon $，则 \(g\) 是 \(f\) 的逆元。
性质
- 两个积性函数的卷积是积性函数。
- 积性函数的逆元是积性函数。
莫比乌斯函数
定义
\[n=\prod _{i=1}^kp_i^{c_i}(p_i\in pirme,p_i\ne p_j)\\ \mu(n)=\left\{ \begin{aligned} 1 & ,& n=1 \\ (-1)^k & ,& \forall c_i=1 \\ 0 & ,& \exists c_i>1 \end{aligned} \right. \]性质
- 莫比乌斯函数是积性函数。
- \(\sum_{i\mid n}\mu(i)=[n=1]\)。
莫比乌斯反演
\[f(x)=\sum_{d|x}g(x)\Leftrightarrow g(x)=\sum_{d|x} \mu(d)f(\frac xd) \]各种卷积结论
\[\varepsilon=\mu*I\Leftrightarrow \varepsilon(n)=[n=1]=\sum_{d|n}\mu(d) \]\[id=\varphi*I\Leftrightarrow id(n)=n=\sum_{d|n}\varphi(d) \]\[d=I*I\Leftrightarrow d(n)=\sum_{d|n} 1 \]\[\sigma=I*id\Leftrightarrow \sigma(n)=\sum_{d|n}d \]拓展
\[\varphi=\mu*id\Leftrightarrow \varphi(n)=\sum_{d|n}d\times\mu(\frac nd) \]推导：\(\mu*id=\mu*\varphi*I=\varepsilon*\varphi=\varphi\)
调和级数枚举
可用来得到每个数的因数，或处理因数有关的问题。
对于每个数，在 \(n\) 内枚举它的倍数，时间复杂度 \(O(n\ln n)\)。
for(int i=1;i<=n;++i)
for(int j=i;j<=n;j+=i)
do something;
埃氏筛
用来处理质因子有关的问题。
对于每个质数，在 \(n\) 内枚举它的所有倍数，时间复杂度是 \(O(n\log\log n)\)。
for(int i:pri)
for(int j=i;j<=n;j+=i)
do something;
欧拉筛
线性筛质数与积性函数。
把每个合数用它的最小质因子筛掉，时间复杂度 \(O(n)\)。
vector<int> pri;
bitset<N> no;
for(int i=2;i<=n;++i){
if(!no[i])pri.push_back(i);
for(int p:pri){
if(i*p>n)break;
no[i*p]=1;
if(i%p==0)break;
}
}
约数个数
\[n=\prod p_i^{c_i} \]\[d(n)=\prod (c_i+1) \]线性筛时需要记录最小质因子的指数。
约数和
\[n=\prod p_i^{c_i} \]\[\sigma(n)=\prod(1+p_i+p_i^2+\dots+p_i^{c_i}) \]线性筛时需要记录最小质因子的 \((1+p+p^2+\dots+p^{c})\)。
素性测试
检测一个数是否是质数。
朴素做法
枚举 \([2,\sqrt n]\) 的整数，看是否有 \(n\) 的因数。
Fermat 素性测试
根据费马小定理，如果 \(n\) 为质数，那么对于 \(a\in[1,n-1]\) 有 \(a^{n-1}\equiv1 \pmod n\)。
我们可以随机 \(C\) 次 \([2,n-1]\) 的数，然后看是否满足条件，\(C\) 可取 \(10\) 左右，记得特判小于 \(3\) 的数。
时间复杂度 \(O(C\log n)\)。
mt19937 rnd(time(0));
bool isprime(int n){
if(n<3)return n==2;
for(int i=1;i<=10;++i){
int a=rnd()%(n-2)+2;
if(qpow(a,n-1,n)!=1) return 0;
}
return 1;
}
分解质因数
朴素做法
枚举 \([2,\sqrt n]\) 的数，看是否是 \(n\) 的因数，当前的数肯定是质数了，时间复杂度 \(O(\sqrt n)\)。
最后如果剩下 \(n>1\) 则剩下的 \(n\) 本身是一个质数。
for(int i=2;i*i<=n;++i){
if(n%i==0){
do something;
while(n%i==0){
do something;
n/=i;
}
}
}
if(n>1){
do something;
}
如果可以预处理出 \(\sqrt n\) 内的质数，则只需枚举质数，而质数个数是 \(O(\frac {n} {\ln n})\) 的，时间复杂度 \(O(\sqrt n+T\frac {\sqrt n}{\ln n})\)。
标签：frac,复习,数论,bmod,基础,varphi,times,sum,gcd From： https://www.cnblogs.com/dccy/p/18499273