数论入门

模运算（mod、%）

概念

取余数(remainder)

$p$ $n$ $n = kp+r$ $k$ $r$ $0\leq r<p$ $n\ mod\ p=\ r$

一些运算

$(a+b)\%p\ =\ (a\%p+b\%p)\%p$
$(a-b)\%p\ =\ (a\%p-b\%p+p)\%p$
$(a\ *\ b)\%p\ =\ ((a\%p)\ * (b\%p))\%p$

除法？

要用到逆元的概念，后面会介绍

一些符号

$d|n$ $d$ $n$ $n\ mod\ d=0$
$a\equiv b\ (mod)\ p$ $a$ $b$ $p$ 同余 $a\ mod \ p = b\ mod\ p$

快速幂

$a,n(0<a,n<1e9)$ $a^n\ mod\ (1e9+7)$

朴素算法


xxxxxxxxxx
int ans=1;
for (int i=1;i<=n;i++){ 
    ans=ans*a%p
}

$O(n)$

快速幂

a^n=\begin{cases} a^{\frac n2}*a^{\frac n2}\ (n\%2==0)\\ a^{\frac{n-1}{2}}*a^{\frac{n-1}{2}}*a\ (n\%2==1)\\ \end{cases}


xxxxxxxxxx
int quick_power(int a,int n,int p){
    if (n==0) return 1;
    if (n%2){
        int tmp=quick_power(a,n/2,p);
        return tmp*tmp%p;
    }else{
        int tmp=quick_power(a,(n-1)/2,p);
        return tmp*tmp%p*a%p;
    }
}
//非递归写法：
int qpow(int a,int b,int p){
    int t=1,y=a;
    while (b>0){
        if (b&1) t=t*y%p%p;
        y=y*y%p%p;
        b>>=1;
    }
    return t;
}

矩阵快速幂
- 矩阵乘法
```
xxxxxxxxxx
a[p][q],b[q][r],c[p][r];
for (int i=1;i<=p;i++)
    for (int j=1;j<=r;j++)
        for (int k=1;k<=q;k++)
            c[i][j]+=a[i][k]*b[k][j]
```
- 递推式与矩阵
  $f_n=f_{n-1}+f_{n-2},f_0=0,f_1=1$
  我们可以构造矩阵
  $A_n=\left[\begin{matrix}f_n&f_{n-1}\end{matrix}\right]\\ B=\left[\begin{matrix}1&1\\1&0\end{matrix}\right]\\ 那么A_n*B=\left[\begin{matrix}f_n,f_{n-1}\end{matrix}\right]*\left[\begin{matrix}1&1\\1&0\end{matrix}\right]=\left[\begin{matrix} f_n+f_{n-1}&f_n \end{matrix}\right]=\left[\begin{matrix} f_{n+1}&f_n \end{matrix}\right]=A_{n+1}\\ A_n*B^k=A_{n+k}$
  $B^k$ $O(log\ n)$ 的复杂度求斐波那契的第n项

最大公因数GCD（Greatest Common Divisor）

概念

$gcd(a,b)$ $a$ $b$ 里面共有的因数中最大的那个

$a$ $b$ $gcd(a,b)=1$

一些性质

$gcd(x,0)=x$
$n$ $0\ mod\ n=0$ $0$ 的因数
$gcd(a,b,c) = gcd(a,gcd(b,c))$
$gcd(a*c,b*c)=c*gcd(a,b)$
$gcd(a,b) = gcd(b,a-b)$
证明：
$gcd(a,b)=1$ $gcd(b,a-b)=1$ ，
$gcd(b,a-b)=d>1$ ，则有
$b=k_1*d$
$a-b=k_2*d$
$(1)+(2)$ $a=(k_1+k_2)*d$ $a$ $b$ $d>1$ $gcd(a,b)=1$ 矛盾
$gcd(a,b)=d$ $a=k_1*d$ $b=k_2*d$ $k_1$ $k_2$ 互质
1. $a=b$ $gcd(a,b)=a=gcd(a,0)=gcd(b,a-b)$
2. $gcd(b,a-b)=gcd(k_2*d,(k_1-k_2)*d)=d*gcd(k_2,k_1-k_2)=d=gcd(a,b)$
$gcd(a,b)=gcd(b,a\ mod\ b)$
证明：
$gcd(a,b)=1$ $gcd(b,a-k*b)=1$ $a-k*b>0$ $k$ 是正整数
$gcd(b,a-k*b)=d>1$ ，则
$b=k_1*d$
$a-k*b=k_2*d$
$(1)+k*(2)$ $a=(k*k_1+k_2)*d$ $a$ $b$ $d>1$ $gcd(a,b)=1$ 矛盾
$gcd(a,b)=d$ $a=k_1*d$ $b=k_2*d$ $k_1$ $k_2$ 互质
1. $a=b$ $gcd(a,b)=a=gcd(a,0)=gcd(b,a\ mod\ b)$
2. $a\ mod\ b = r$ $k$ $a-k*b=r$
  $gcd(b,a\ mod\ b)=gcd(k_2*d,r)=gcd(k_2*d,(k_1-k*k_2)*d)=d*gcd(k_2,k_1-k*k_2)=gcd(a,b)$

求法

辗转相除法(欧几里得算法)：


xxxxxxxxxx
int gcd(int a,int b){
    if (b == 0) return a;
    else return gcd(b,a%b);
}
//写成一行：
int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b) }

$O(log\ n)$

$a>b$ $a\ mod\ b<\frac a2$
$a>2*b$ $a\ mod\ b < b < \frac a2$
$a < 2*b$ $a\ mod\ b = a-b<a-\frac a2=\frac a2$
$gcd(a,b)$ $gcd(b,a\%b)$ $gcd(a\%b,b\%(a\%b))$ ，
$a\%b+b\%(a\%b)<\frac a2+\frac b2$
$a+b$ $a+b$ 的值指数级减小

例题

求线段上的整点个数
$A(x_1,y_1),B(x_2,y_2)$ $AB$ 上的整点个数
$x=|x_1-x_2|,y=|y_1-y_2|,gcd(x,y)=d,x=k_1*d,y=k_2*d$
$AB$ $(a,b)$
$\frac ba = \frac yx=\frac{k_2*d}{k_1*d}=\frac{k_2}{k_1}$
$b=\frac{a*k_2}{k_1}$
$a,0<=a<=x$ $b$ 是一个整数
$k_1$ $k_2$ $a$ $k_1$ 的倍数
$ans=\frac{x}{k_1}+1=d+1$
$S=a+\frac b2-1$

扩展欧几里得算法(exgcd)

概念

$a$ $b$ $x$ $y$ $ax+by=gcd(a,b)$
$(x,y)$

求法

$a$ $b$
$gcd(a,b)=gcd(b,a\%b)=gcd(b,a-\lfloor \frac ab \rfloor b)$
$x$ $y$ $ax+by=gcd(a,b)$
$x'$ $y'$ $bx'+(a-\lfloor \frac ab \rfloor b)y'=gcd(b,a-\lfloor \frac ab \rfloor b)$
$a$ $b$ $x$ $y$ $b$ $a\%b$ $x'$ $y'$ ”
$ax+by=bx'+(a-\lfloor \frac ab \rfloor b)y'$
$a(x-y')+b(y-(x'-\lfloor \frac ab \rfloor y'))=0$
$a$ $b$ $x=y',y=x'-\lfloor \frac ab \rfloor y'$
$b=0$ $x=1，y=0$


xxxxxxxxxx
int exgcd(int a, int b, int& x, int& y){
    if (b==0){
        x = 1;
        y = 0;
        return a;
    }else{
        int d=exgcd(b, a%b, y, x);
        y = y - a/b*x;
        return d;
    }
}

应用

$a，b，c$ $ax+by=c$
1. $c=gcd(a,b)$ $(x_0,y_0)$ ，
  $x=x_0+\frac{b}{c}*t,y=y_0-\frac{a}{c}*t,t为任意整数$
2. $c=k*gcd(a,b)$
  $x=(x_0+\frac{b}{c}*t)*k,y=(y_0-\frac{a}{c}*t)*k,t为任意整数$
3. 其他情况无解

求乘法逆元

$\frac ba\%p$
$\frac ba\%p=b*\frac 1a \%p$
$\frac 1a \%p$
$\frac 1a\%p = x$
$1\%p=a*x\%p=1$
$a,p$ $x$ $a*x\%p=1$ $ax\equiv1(mod\ p)$ $x$ $a$ $p$ 意义下的乘法逆元
$ax=kp+1$
$ax-kp=1$
$gcd(a,p)=1$ $(x,k)$ 存在


xxxxxxxxxx
int reverse(int a,int p){
    int x,y;
    if (exgcd(a,p,x,y)==1)
        return (x%p+p)%p;//使x落在[0,p-1]内
    else 
        return 0;  //逆元不存在
}

解模线性方程组

$lcm(a,b)=\frac{ab}{gcd(a,b)}$

模线性方程组：

\begin{cases} x\equiv r_1(mod\ p_1)\\ x\equiv r_2(mod\ p_2)\\ ...\\ x\equiv r_n(mod\ p_n)\\ \end{cases}

考虑前两个方程,有\\ \begin{cases} x=k_1p_1+r_1\\ x=k_2p_2+r_2\\ \end{cases}\\ 则k_1p_2+r_1=k_2p_2+r_2\\ k_1p_1-k_2p_2=r_2-r_1\\ 可以用exgcd求出k_1,k_2\\ 将k_1,k_2带入求出前两个方程的特解x_0\\ 前两个方程的通解为x=x_0+k*lcm(p1,p2)\\ 即x\equiv x_0(mod\ lcm(p_1,p_2))\\ 至此，我们合并了前两个方程，可以按这个方法合并剩余的方程

中国剩余定理CRT（Chinese Remainder Theorem）

也是用来求解模线性方程组的，但是要求模数两两互质

设M=\prod_{i=1}^{n}m_i,M_i=\frac{M}{m_i}\\ 设t_i为M_i模m_i意义下的逆元，即M_it_i\equiv 1(mod \ m_i)\\ 方程的通解为x=kM+\sum_{i=1}^{n}{r_it_iM_i}\\

费马小定理

$p$ $a$ $p$ $a^{p-1}\equiv 1(mod\ p)$

费马小定理求乘法逆元:

$x$ $a$ $p$ $ax \equiv 1(mod\ p)$

$a*a^{p-2}\equiv a^{p-1}\equiv 1(mod\ p)$

$x=a^{p-2}\ mod\ p$


xxxxxxxxxx
int inverse(a,p){
    return qpow(a,p-2,p);
}

素数筛

朴素筛法


xxxxxxxxxx
int cnt=0;
bool is_prime[N];
for (int i=2;i<N;i++){
    int flag=1;
    for (int j=2;j*j<=i;j++){
        if (i%j==0){
            flag=0;
            break;
        }
    }
    is_prime[i]=flag;
}

$O(n\sqrt n)$

埃氏筛法


xxxxxxxxxx
int prime[N];
for (int i=2;i<N;i++) is_prime[i]=1;
for (int i=2;i<N;i++){
    if (is_prime[i]) prime[cnt++]=i;
    for (int j=2;j*i<N;j++){
        is_prime[i*j]=0
    }
}

$O(nloglogn)$

欧拉筛（线性筛）


xxxxxxxxxx
for (int i=2;i<N;i++) is_prime[i]=1;
for (int i=2;i<N;i++){
    if (is_prime[i])
        prime[cnt++]=i; 
    for (int j=0;j<cnt&&i*prime[j]<N;j++){
        is_prime[i*prime[j]]=0;
        if (i%prime[j]==0)
            break;  
    }
}

$O(n)$

OEIS

http://oeis.org/

Project Eula

https://projecteuler.net/