数论学习小记 DAY1 基础数论

省选两天出了两道数论，连暴力都不会打。回头一看确实自己的数论什么都不会。从头学起，开博客记录一下。立一个flag：半个月学完数论

基础数论

1.欧几里得和扩展欧几里得

先说几个简单的概念。

• 整除：定义如下：设a是非零整数，b是整数，若存在一个整数q，使得 b=a×q $b=a\times q$ 则称b可被a整除，记作 a|b $a|b$，称b是a的倍数，a是b的因数。下面有几个常用性质。

  • 传递性：若 a|b,b|c $a|b,b|c$，则 a|c $a|c$.
  • a|b且b|c $a|b且b|c$ ⇔ $\iff$ ∀x,y $\mathrm{\forall }x,y$，有 a|(b×x+c×y) $a|(b\times x+c\times y)$.
  • 设 m≠0 $m\ne 0$，则 a|b⇔(m×a)|(m×b) $a|b\iff (m\times a)|(m\times b)$.
  • 设整数x和y满足 a×x+b×y=1 $a\times x+b\times y=1$ 且 a|n,b|n $a|n,b|n$，那么 (a×b)|n $(a\times b)|n$.
    
    • 证明：因为 a|n,b|n $a|n,b|n$,所以
    • (a×b)|(b×n),(a×b)|(a×n) $(a\times b)|(b\times n),(a\times b)|(a\times n)$ （性质三）
    • 所以 (a×b)|(a×n×x+b×n×y) $(a\times b)|(a\times n\times x+b\times n\times y)$（性质二）
    • 其中 a×n×x+b×n×y=n×(a×x+b×y)=n×1=n $a\times n\times x+b\times n\times y=n\times (a\times x+b\times y)=n\times 1=n$.得证。
  • 若 b=q×d+c $b=q\times d+c$，那么 d|b $d|b$的充要条件是 d|c $d|c$

• 同余：若a,b为两个整数，且他们的差 a−b $a-b$能被某个自然数m整除，称a在模m意义下与b同余，记作 a≡b (mod m) $a\equiv b(modm)$，它意味着 a−b=m×k(k∈N+) $a-b=m\times k(k\in N_{+})$。下面有几个常用性质：

  • 自反性，对称性，传递性，同加（乘/幂）性
  • a×b mod k=(a mod k)×(b mod k) mod k $a\times bmodk=(amodk)\times (bmodk)modk$.
  • 若 a mod p=x,a mod q=x,gcd(p,q)=1,则a mod (p×q)=x $amodp=x,amodq=x,gcd(p,q)=1,则amod(p\times q)=x$
    
    • 证明：因为 a mod p=x,a mod q=x $amodp=x,amodq=x$.
    • 则一定 ∃s,t∈N $\mathrm{\exists }s,t\in N$,使得 a=s×p+x,a=t×q+x $a=s\times p+x,a=t\times q+x$
    • 所以 s×p=t×q $s\times p=t\times q$
    • 因为gcd(p,q)=1，故t中必有p这个质因子
    • 所以 ∃r,使s=r×q $\mathrm{\exists }r,使s=r\times q$
    • 所以 a=r×p×q+x,a mod p×q=x $a=r\times p\times q+x,amodp\times q=x$.
  • 若 ac≡bc (mod p)且gcd(p,c)=1,则a≡b (mod p) $ac\equiv bc(modp)且gcd(p,c)=1,则a\equiv b(modp)$
• 最大公约数和欧几里得算法
  
  • 最大公约数：设 a=pk11pk22pk33...pknn,b=pt11pt22pt33...ptnn，p为质数，k,t∈N $a=p_1^{k_1}{p}_2^{k_2}{p}_3^{k_3}...p_n^{k_n},b=p_1^{t_1}{p}_2^{t_2}{p}_3^{t_3}...p_n^{t_n}，p为质数，k,t\in N$，则 a和b的最大公约数（记作gcd(a,b)或(a,b)）=pmin(k1,t1)1pmin(k2,t2)2...pmin(kn,tn)n $a和b的最大公约数（记作gcd(a,b)或(a,b)）=p_1^{min(k_1,t_1)}{p}_2^{min(k_2,t_2)}...p_n^{min(k_n,t_n)}$，该定义可以推广到多个数。
  • 欧几里得算法（辗转相除法）： gcd(x,y)=gcd(x,y−x) $gcd(x,y)=gcd(x,y-x)$
    
    • 证明：若 ∃z|x,z|y,则z|(y−x)，反之z一定不是(y−x)和x的公因子 $\mathrm{\exists }z|x,z|y,则z|(y-x)，反之z一定不是(y-x)和x的公因子$。
    • 代码：

        int gcd(int x,int y)
        {
            return !y?x:gcd(y,x%y);
        } 

进入正题，扩展欧几里得算法

扩展欧几里得算法是用来在已知a,b时，求解一组p,q，使得 p×a+q×b=gcd(a,b) $p\times a+q\times b=gcd(a,b)$

如何求解呢？回想起刚才的gcd，我们列出如下等式。

p×a+q×b=gcd(a,b)=gcd(b,a%b)=p×b+q×(a%b)=p×b+q×(a−a/b×b）=q×a+(p−a/b×q)×b) $$p\times a+q\times b=gcd(a,b)=gcd(b,a\mathrm{\%}b)=p\times b+q\times (a\mathrm{\%}b)=p\times b+q\times (a-a/b\times b）=q\times a+(p-a/b\times q)\times b)$$

int ex_gcd(int a,int b,int &x,int &y)
{
    if (!b)
    {
        x=1,y=0;
        return a;
    }
    int ret=ex_gcd(b,a%b,x,y);
    int tmp=x;x=y;y=tmp-a/b*y;
    return ret;
}
int main()
{
    int a,b,x,y,z;
    scanf("%d%d",&a,&b);
    z=ex_gcd(a,b,x,y);
    printf("%d %d %d\n",x,y); //x*a+y*b=gcd(a,b)
    return 0;
}

求解线性同余方程
定理：对于方程 a×x+b×y=c⇔a×x≡c (mod b) $a\times x+b\times y=c\iff a\times x\equiv c(modb)$，有整数解的充要条件是 c%gcd(a,b)=0 $c\mathrm{\%}gcd(a,b)=0$
对于线性同余方程的一般形式 a×x+b×y=c $a\times x+b\times y=c$,我们只需要先求出一组方程 a×x0+b×y0=gcd(a,b) $a\times x_0+b\times y_0=gcd(a,b)$,然后我们将等式的两边同时乘以一个 cgcd(a,b) $\frac{c}{gcd(a,b)}$,就得出了原方程的一组解。

定理2：对于上述方程，若已知一组解 (x0,y0) $(x_0,y_0)$，方程所有解为： x=x0+b×t,y=y0−a×t,t∈N $x=x_0+b\times t,y=y_0-a\times t,t\in N$

应用定理2，我们就可以得出所有的解，在实际应用中，往往会求最小整数解，也就是最小化x，此时 t=b/gcd(a,b),x=(x%t+t)%t $t=b/gcd(a,b),x=(x\mathrm{\%}t+t)\mathrm{\%}t$.

逆元

若 a×x≡1 (mod b),gcd(a,b)=1 $a\times x\equiv 1(modb),gcd(a,b)=1$互质，则称x为a在模p意义下的逆元，记作 a−1 $a^{-1}$.

求逆元的几个方法：
- 扩展欧几里得求解： a×x≡1 (mod b),gcd(a,b)=1⇔a×x+b×y=1 $a\times x\equiv 1(modb),gcd(a,b)=1\iff a\times x+b\times y=1$,将上面的式子带入扩展欧几里得中，求出的x就是逆元
- 递推： A[i]=−(p/i)∗A[p%i] $A[i]=-(p/i)\ast A[p\mathrm{\%}i]$。。。。证明略
- 费马小定理/欧拉定理。

中国剩余定理

设自然数 m1,m2,m3...mr $m_1,m_2,m_3...m_r$两两互质，记 M=m1×m2×m3×...mr $M=m_1\times m_2\times m_3\times ...m_r$,则同余方程组

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪x≡b1 (mod m1)x≡b2 (mod m2)x≡b3 (mod m3)⋮x≡br (mod mr) $$\{\begin{array}{l}x\equiv b_1(mod{m}_1)\\ x\equiv b_2(mod{m}_2)\\ x\equiv b_3(mod{m}_3)\\ ⋮\\ x\equiv b_r(mod{m}_r)\end{array}$$

在模M同余意义下有唯一解
求解方法：
令 Mi=M/mi,ti=M−1i即Mi在模mi意义下的逆元 $M_i=M/m_i,t_i=M_i^{-1}即M_i在模m_i意义下的逆元$
在模M意义下，方程组的解为

(∑i=1naitiMi) mod M $$(\underset{i=1}{\overset{n}{\sum }}{a}_i{t}_i{M}_i)modM$$

卡特兰数

卡特兰数是组合学中计数问题经常出现的数列，其前几项为1,2,5,14,42,132…
卡特兰数第n项求法：
1. 递归公式(1):

f(n)=∑i=0n−1f(i)×f(n−i−1) $$f(n)=\underset{i=0}{\overset{n-1}{\sum }}f(i)\times f(n-i-1)$$

2. 递归公式(2):

f(n)=f(n−1)×(4×n−2)n+1 $$f(n)=\frac{f(n-1)\times (4\times n-2)}{n+1}$$

3. 组合公式(1):

f(n)=(2nn)n+1 $$f(n)=\frac{(\genfrac{}{}{0ex}{}{2n}{n})}{n+1}$$

4. 组合公式(2):

f(n)=(2nn)−(2nn−1) $$f(n)=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n-1})$$

常用模型：二叉树计数，括号序列，出栈序列

素数相关

素数定义：一个大于1的正整数，如果除了1和它本身之外，没有任何因数，则称其为质数或素数。1既不是质数也不是合数。素数有无穷多个。

素数的相关定理

• 唯一分解定理
  
  • 若整数 a≥2 $a\ge 2$,那么a一定可以表示为若干个质数的乘积且唯一，形如
    a=p1p2p3p4...ps $$a=p_1{p}_2{p}_3{p}_4...p_s$$
• 威尔逊定理
  
  • 若p为素数，则
    (p−1)!≡−1 (mod p) $$(p-1)!\equiv -1(modp)$$
    逆定理同样成立。
• 费马小定理
  
  • 若p为素数，a为正整数，且 gcd(a,p)=1 $gcd(a,p)=1$,则
    ap−1≡1 (mod p) $$a^{p-1}\equiv 1(modp)$$
  • 证明：易知 a,2a,3a...(p−1)a $a,2a,3a...(p-1)a$没有一个数是p的倍数，其次上述p-1个数中没有任何两个在模p意义下同余。
  • 故p-1个数对在模p意义下的同余是1…p-1的某一种排列，即
    a×2a×3a×...×(p−a)a≡1×2×...×(p−1) (mod p) $$a\times 2a\times 3a\times ...\times (p-a)a\equiv 1\times 2\times ...\times (p-1)(modp)$$
    化简得：
    ap−1×(p−1)!≡(p−1)! (mod p) $$a^{p-1}\times (p-1)!\equiv (p-1)!(modp)$$

素数的相关知识

• 欧拉函数 φ(n) $\phi (n)$表示小于等于n的数中与n互质的数的个数。于是有如下定理。
  
  • 欧拉函数是一个积性函数。
    
    • 若n是素数，则 φ(n)=n−1 $\phi (n)=n-1$
    • 若n是某个素数的整次幂即 n=pa $n=p^a$，则 φ(n)=(p−1)×pa−1 $\phi (n)=(p-1)\times p^{a-1}$
    • 若n是两个互质的数a,b的乘积即 n=a×b且gcd(a,b)=1 $n=a\times b且gcd(a,b)=1$，则 φ(n)=φ(a)×φ(b) $\phi (n)=\phi (a)\times \phi (b)$
  • 设 n=pa11×pa22×...×pakk $n=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k}$，则
    φ(n)=n×(1−1p1)×(1−1p2)×...×(1−1pk) $$\phi (n)=n\times (1-\frac{1}{p_1})\times (1-\frac{1}{p_2})\times ...\times (1-\frac{1}{p_k})$$
  • 欧拉定理
    aφ(p)≡1 (mod p) $$a^{\phi (p)}\equiv 1(modp)$$
• 素数的判定
  
  • 单个数
    
    • 穷举法：从 1——n−−√ $1——\sqrt{n}$枚举并试除。复杂度差劲
    • Miller-Rabin算法：一种基于随机化的检验质数的方法，选取合适的检验用数(2,7,61,24251)可以让失误率极极极极极极低。

const int prime[5]={0,2,7,61,24251};
ll quick_mul(ll a,ll b,ll Mod)
{
    ll ans=0;a%=Mod,b%=Mod;
    while (b)
    {
        if (b&1) ans+=a,ans%=Mod;
        b/=2,a+=a,a%=Mod;
    }
    return ans;
}
ll quick_pow(ll a,ll b,ll Mod)
{
    ll ans=1;a%=Mod,b%=Mod;
    while (b)
    {
        if (b&1) ans*=a,ans%=Mod;
        b/=2,a*=a,a%=Mod;
    }
    return ans;
}
bool check(ll r,ll m,ll x,ll a)
{
    ll res=quick_pow(a,m,x);
    if (res==x-1 || res==1) return 1;
    while (r--)
    {
        res=quick_mul(res,res,x);
        if (res==x-1) return 1;
    }
    return 0;
}
bool Miller_Rabin(ll x)
{
    if (x==2) return 1;
    if (x==1 || x%2==0) return 0;
    ll m=x-1,r=0;
    while (!(m&1))
        m/=2,r++;
    for (int i=1;i<=4;i++)
    {
        int a=prime[i];
        if (x==a) return 1;
        if (x%a==0) return 0;
        if (!check(r,m,x,a)) return 0;
    }
    return 1;
}

• 筛法
  
  • 埃氏筛：将所有质数不大于n的倍数全部筛去，有冗余计算。
  • 线性筛：在适当的地方break，保证每个数只被筛去一次。

void get_prime(int n)
    visit[1]=1; 
    for (int i=2;i<=n;i++)
    {
        if (!visit[i])
            a[++cnt]=i;
        for (int j=1;j<=cnt && i*a[j]<=n;j++)
        {
            visit[i*a[j]]=1;
            if (i%a[j]==0)
                break;
        }
    }
}

• Pollard Rho求大数质因子
  
  • 原理：基于随机的算法。
  • 我们知道，在[1,n]中随机一个数，使这个数是n的因数的概率是很小的。但是如果随机两个数并做差，那么概率将会大大提高。
  • 那设随机的两个数为 x1,x2 $x_1,x_2$，使得 gcd(|x1−x2|,n)>1 $gcd(|x_1-x_2|,n)>1$的概率就会大。
  • 所以就有了如下算法：
    
    • 随机一个 x1∈[1,n] $x_1\in [1,n]$， x2 $x_2$则通过公式 x2=(last_x22+c)%n $x_2=({last\mathrm{\_}{x}_2}^2+c)\mathrm{\%}n$算出，其中c为任意给定值。
    • 若满足 gcd(|x1−x2|,n)>1 $gcd(|x_1-x_2|,n)>1$，则证明 x1−x2 $x_1-x_2$是n的一个因数，若其是质数，则记录，否则递归的继续计算。
    • 判断素数使用Miller-Rabin算法。

const int prime[5]={0,2,7,61,24251};
vector <int> f;
ll quick_mul(ll a,ll b,ll Mod)
{
    ll ans=0;
    while (b) {if (b&1) ans+=a,ans%=Mod;a+=a;b/=2;a%=Mod;}
    return ans;
}
ll quick_pow(ll a,ll b,ll Mod)
{
    ll ans=1;
    while (b) {if (b&1) ans*=a,ans%=Mod;a*=a,b/=2,a%=Mod;}
    return ans;
}
ll gcd(ll a,ll b)
{
    return !b?a:gcd(b,a%b);
}
bool check(ll r,ll m,ll x,ll pri)
{
    ll res=quick_pow(pri,m,x);
    if (res==x-1 || res==1) return 1;
    while (r--)
    {
        res=quick_mul(res,res,x);
        if (res==x-1) return 1;
    }
    return 0;
}
bool Miller_Rabin(ll x)
{
    if (x==2) return 1;
    if (x==1 || !(x&1)) return 0;
    int m=x-1,r=0;
    while (!(m&1))
        m/=2,r++;
    for (int i=1;i<=4;i++)
    {
        int pri=prime[i];
        if (x==pri) return 1;
        if (!(x%pri)) return 0;
        if (!check(r,m,x,pri)) return 0;
    }
    return 1;
}
ll Pollard_Rho(ll n,ll c)
{
    ll _x1=rand()%n+1,_x2=_x1;
    ll i=1,k=2;
    while (1)
    {
        i++;
        _x1=(_x1*_x1+c)%n;
        ll t=abs(_x1-_x2);
        ll g=gcd(t,n);
        if (_x1==_x2) return n;
        if (g>1 && g!=n) return g;
        if (i==k)
            _x2=_x1,k*=2;
    }
}
void get(ll n)
{
    if (Miller_Rabin(n))
    {
        f.push_back(n);
        return ;
    }
    ll p=n;
    while (p>=n) p=Pollard_Rho(p,rand()%(n-1)+1);
    get(p);
    get(n/p);
}