基础概念

整除性

称一个整数 a 能被一个整数 b(b!=0) 整除，假设存在第三个整数 c 使得 a=bc ，用记号 a|b 表示 a 能整除 b 或 b 是 a 的一个因子。显然对于每一个整数 a 都有 1|a,a|a 并对所有的 b 有 b|0(b!=0)

还可以推出如下性质：

a|b,b|c->a|c
a|b->ac|bc(b!=0)
a|b,a|c->a|(mb+nc),a|bc

如果 a 不能被 b 整除并存在唯一的 k 和 c<b 使得 a=bk+c 称 c 为 a 除以 b 的余数记做 a mod b=c

质数和合数

质数又称素数，记恰好包含两个不同的因子的整数（1 和其本身）。需要注意的是 1 不是质数，2 是最小的质数且为唯一的偶质数

合数则是素数之外剩下的数，即除了 1 和本身之外还能被其他数整除

注意：质数有无数多个，证明很啰嗦

互质数和互质自然数

互质数指公约数只有 1 的两个整数，又称互质整数

例：3 和 8 ，1 和 10 ，4 和 5

互质自然数指公约数只有 1 的两个自然数，是互质数的特例

注意：

数其本身绝对不是互质数，因为除了 1 这个公约数还有其本身，但是1特例
另外 1 和任何数都互为互质数
互为互质数的两个数本身未必是质数

同余与剩余

如果说 m 是 x-a 的一个因子，就说 x 和 a 关于模 m 同余，并记为 x≡a(mod m) 。 a 称为 x 模 m 的一个剩余。如果 0<=a<=m-1 ，那么 a 称为 x 模 m 的最小剩余。模 m 的一个剩余类是有与某个给定的剩余（ mod m ）同余的所有数组成的一个类。显然总共有m个剩余类他们分别由 0,1,2,...,m-1 代表。任何 m 个剩余类的数组成的一个集合都称为模 m 的一个完全剩余系，简称完系

定理：若 r1,r2,...,rm 是模 m 的一个完全剩余系，且正整数 a 满足 (a,m)=1 。则对任意整数 b 有ar1+b,ar2+b,...,arm+b 构成一个完全剩余系

算术基本定理

每个大于 1 的自然数均写为质数的积，而且这些质数因子按大小排列后写法仅有一种方法，或者说任意一个数n可以唯一地写为若干个质数的幂的乘积的形式。很多算法的正确性都依赖于它

例如：20=2*2*5 ，6=2*3

模运算规则

基本运算规则

(a+b)%p=(a%p+b%p)%p 
(a-b)%p=(a%p-b%p)%p 
(a*b)%p=(a%p*b%p)%p 
(a^b)%p=((a%p)^b)%p

注意：模运算的除法不支持上述规则

推论

1
2
3

若a≡b(%p),则对于任意的c,都有(a+c)≡(b+c)(%p)
若a≡b(%p),则对于任意的c,都有(a*c)≡(b*c)(%p)
若a≡b(%p),c≡d(% p),则(a+c)≡(b+d)(%p),(a-c)≡(b-d)(%p),(a*c)≡(b*d)(%p),(a/c)≡(b/d)(%p)

费马小定理

下文有详细讲解

1 2	若p是素数，a是正整数且不能被p整除，则a^(p-1)≡1(%p) 推论:若p是素数，a是正整数且不能被p整除，则a^p≡a(%p)

素数筛

分类

在刚接触编程时对于寻找素数第一时间便是想到二重循环暴力查找，在数论学习中即将学习时间复杂度为 O(nloglogn) 的埃氏筛法进行大量素数查找，但是当数据范围达到 1e7 数量级时则需要更高效的时间复杂度为 O(n) 的线性筛（又称欧拉筛）

枚举法

问题：查找 [l,r] 中的素数个数

时间复杂度：O(n²)

如果只是判断某个数是否为素数用优化后的 O(√n) 的素数判断函数足矣，判断多个数还是用下面的高效筛法吧

#include<bits/stdc++.h>
using namespace std;

bool prime(int n){//判断素数函数,时间复杂度为O(n)
    if(n==1)return 0;//特判
    for(int i=2;i*i<=n;i++){//TLE的话,改用tot=sqrt(n),i<=tot,因为这样只用算一次
        if((n%i)==0)return 0;
    }
    return 1;
}

signed main()
{
    int l,r;cin>>l>>r;
    int cnt=0;//计数器
    vector<int> vec;//存储素数
    for(int i=1;i<=r;i++){
        if(prime(i)){
            cnt++;
            vec.push_back(i);
		}
	}
    cout<<cnt<<endl;//输出个数
    for(auto x:vec)cout<<x<<" ";//输出素数
    return 0;
}

埃氏筛法

问题：查找 0~n 之间所有的素数个数

时间复杂度：O(nlognlogn)

埃拉托斯特尼筛法，简称埃氏筛法。是对多个整数进行素性检查更加高效的算法，它是一个与辗转相除法一样古老的算法，可以用于枚举 n 以内的素数

首先，我们将 2 到 n 范围内的所有整数写下来。其中最小的数字 2 是素数。将表中所有 2 的倍数都划去。表中剩余的最小数字是3，它不能被更小的数整除，所以是素数。再将表中所有3的倍数都划去。依此类推，如果表中剩余的最小数字是 m 时，m 就是素数。然后将表中所有 m 的倍数都化去。像这样反复操作，就能依次枚举 n 以内的素数

时间复杂度基本接近线性，一般题用这个筛法足矣

#include<bits/stdc++.h>
using namespace std;

const int maxn=10005;
int prime[maxn];//prime[i]存储0~n内第i个素数
bool is_prime[maxn+1];//辅助函数：is_prime[i]为true时表示i是素数

//返回n以内素数的个数
int sieve(int n){
    int p=0;
    for(int i=0;i<=n;i++)is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            prime[++p]=i;
            for(int j=2*i;j<=n;j+=i)is_prime[j]=false;//筛去所有素数的倍数
        }
    }
    return p;
}


signed main()
{
    int n;//枚举n以内素数
    while(cin>>n){
       int p=sieve(n);
        cout<<p<<endl;//输出个数
        for(int i=0;i<p;i++)//输出素数
        cout<<prime[i]<<" ";
        cout<<endl;
    }
    return 0;
}

区间筛法

问题：查找 [l,r)(2<=l<r) 内的素数个数

时间复杂度：不清楚不会算

因为b以内合数的最小质因数一定不超过 sqrt(b) ，如果有 sqrt(b) 以内的素数表的话，就可以把筛选法用在 [a,b) 上了,先分别做好 [2,sqrt(b)) 的表和 [a,b) 的表，然后从 [2,sqrt(b)) 的表中筛得素数的同时，也将其倍数从 [a,b) 的表中划去，最后剩下的就是区间 [a,b) 内的素数了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10005;

bool is_prime[maxn];//标记0~sqrt(b)内的素数
bool is_prime_small[maxn];//标记a~b内的素数(注意数组从0开始)

void segment_sieve(ll a,ll b) {
    for(ll i=0;i*i<b;++i) 
    is_prime_small[i]=true;//初始化
    for(ll i=0;i<b-a;++i) 
    is_prime[i]=true; //初始化,注意下标变化,为了省空间
     for(ll i=2;i*i<b;++i){
         if(is_prime_small[i]){
             for(ll j=2*i;j*j<b;j+=i) 			
             	is_prime_small[j]=false; //筛选[2,sqrt(b));
                //(a+i-1)/i得到最接近a的i的倍数，最低是i的2倍，然后筛选
             for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i)//数字后面+LL表示类型转为ll
                 is_prime[j-a]=false;
         }
     }
}

signed main()
{
    int a,b;
    while(cin>>a>>b){
        segment_sieve(a,b);
        int cnt=0;//计数器
        for(int i=a;i<b;i++){//输出素数
            if(is_prime[i-a]){
                cnt++;
                cout<<i<<" ";
            }
        }
        cout<<endl;
        cout<<cnt<<endl;//输出个数
    }
    return 0;
}

欧拉线性筛法

问题：查找 0~n 之间所有的素数个数

时间复杂度：O(n)

埃氏筛法很多数被处理了不止 1 遍。比如 6 在素数为 2 的时候处理 1 次，在 3 时候又处理一次，因此又造成了不必要处理。本代码保证每个合数只会被它的最小质因数筛去，因此每个数只会被标记一次

核心代码：if(i%prime[j]==0)break;

欧拉筛的难点就在于对 if(i%prime[j]==0) 这步的理解，当 i 是 prime[j] 的整数倍时记 m=i/prime[j] ，那么 i*prime[j+1] 就可以变为 (m*prime[j+1])*prime[j] ，这说明 i*prime[j+1] 是 prime[j] 的整数倍，不需要现在筛出，因为在之后筛除过程中 i*prime[j+1] 这个合数一定会被 prime[j] 筛除，prime[j] 之后的所有素数同理，所以 break 跳出循环。

原理：欧拉定理下面有讲

#include<bits/stdc++.h>
using namespace std;
 
const int maxn=1e6+10;
int cnt;//记录已知素数数量
vector<int> vec;//存放素数的不定长数组
bool is_prime[maxn];//筛除标记，最大标记到maxn-1
 
int main()
{
    int n;
    while(cin>>n){
        for(int i=0;i<=n;i++)
        is_prime[i]=true;
        vec.clear();
        cnt=0;
        is_prime[0]=is_prime[1]=false;//0和1都不是素数
        
        for(int i=2;i<=n;i++){
            if(is_prime[i]){
                vec.push_back(i);
                cnt++;
            }
            for(int j=0;j<cnt&&i*vec[j]<=n;j++){
                is_prime[i*vec[j]]=false;//筛除
                if(i%vec[j]==0)break;//关键代码
            }
        }
        cout<<vec.size()<<endl;
        for(auto x:vec){
            cout<<x<<" ";
        }
    }
    return 0;
}

欧几里得及其拓展定理

欧几里得定理

参考博客欧几里得算法又称作辗转相除法，gcd 函数 (求最大公因数）书写有多种方法

基本定理：对于非负整数 a 和 b，设 a=qb+r ，其中 a,b,q,r 都是整数，则 gcd(a,b)=gcd(b,r) ，即 gcd(a,b)=gcd(b,a%b)

应用

求最大公因式模板

三目运算符压缩（较快） a 和 b 都可以是 0

1
2
3

inline int gcd(int a,int b) {
    return b>0 ? gcd(b,a%b):a;
}

位运算（超快）a 可以是 0 但是 b 不能是 0

inline int gcd(int a,int b) {
    while(b^=a^=b^=a%=b);
    return a;
}

gcd库函数（较慢）a 和 b 都可以是 0

#include<algorithm>
inline int gcd(int a,int b) {
	return __gcd(a,b);
}

求最小公倍数模板

1
2
3

inline lcm(int a,int b){
	return a*b/gcd(a,b);
}

裴蜀定理

对于任何整数 a 、b 和它们的最大公约数 d ，关于未知数的 x 和 y 的线性丢番图方程 ax+by=m ：当且仅当 m 是 d 的倍数时有整数解且解为无穷多个，我们可以借助扩展欧几里得的 q 求解不定方程求出其中一组解

扩展欧几里得定理

参考博客这篇转载的博客讲的比较全，但是太乱了还是自己总结一下（不给证明了）

基本算法：对于不完全为 0 的非负整数 a 和 b，gcd(a,b) 表示 a ， b 的最大公约数，必然存在整数对 x 和 y ，使得 gcd(a,b)=ax+by

注意：相较之前的欧几里得定理该定理的范围更加严格，a 和 b 不能同时为 0

模板

a 和 b 都可以是 0 但是不能同时为 0

#include<bits/stdc++.h>
using namespace std;

//找到一组解x,y,使得ax+by=gcd(a,b)并返还gcd(a,b)
int exgcd(int a,int b,int &x,int &y){//注意&,否则最后就取不到要求的x,y了
    if(b==0){
        x=1;
        y=0;
        return a;
    }
	int r=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
    y=t-a/b*y;
    return r;
}

signed main()
{
    int a,b,x,y;
    cin>>a>>b;
    int tot=exgcd(a,b,x,y);
    cout<<x<<" "<<y<<" "<<tot<<endl;
    return 0;
}

应用

扩展欧几里得定理的应用主要有一下三个方面：

求解不定方程
求解模线性方程（线性同余方程）
求解模的逆元（在逆元部分讲解）

这三个应用其实根源还是借助了扩展欧几里得定理的模板解决

求解不定方程

定理：若是 c mod gdc(a,b)=0 ，则方程存在整数解（无穷多个）

不定方程其实就是方程等式右边的数 c 是随机给定的一个数，它可能是关于 gcd(a,b) 的一个倍数，也可能不是，或者就是 gcd(a,b) 本身

解法：

先找到 ax+by=gcd(a,b) 的解 x0 和 y0
判断 c%gcd(a,b)==0 ，是的话将上述方程乘上一个系数转换为 ax+by=c 得到的新的 (x,y) 就是方程的一对整数解，不是就算了

#include<bits/stdc++.h>
using namespace std;

//找到一组解x,y,使得ax+by=gcd(a,b)并返还gcd(a,b)
int exgcd(int a,int b,int &x,int &y){//注意&,否则最后就取不到要求的x,y了
    if(b==0){
        x=1;
        y=0;
        return a;
    }
	int r=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
    y=t-a/b*y;
    return r;
}

bool linear_equation(int a,int b,int c,int &x,int &y){//同样也要用&关联
	int d=exgcd(a,b,x,y);
	if(c%d)
	return false;
	int k=c/d;
	x*=k;//求出不定方程的解
	y*=k;
	return true;
}

signed main()
{
    int a,b,c,x,y;
    cin>>a>>b>>c;
    int tot=linear_equation(a,b,c,x,y);
    if(tot){//求出一组整数解即可
        cout<<"YES"<<endl;
        cout<<x<<" "<<y<<endl;
    }
    else cout<<"NO"<<endl;
    return 0;
}

对于该方程其他的整数解满足下列关系式：

求解模线性方程

定理：当且仅当 gcd(a,n)|b 时，同余方程 ax≡b(mod n) 对于未知数 x 有解，并且方程有 gcd(a,n) 个解

证明逻辑性很强，回头还是有必要看看死记硬背总是忘

解法：求解 ax≡b(mod n) 相当于求解方程 ax+ny=b(x,y为整数) ，所以问题转化为了求解不定方程的一种情况

先求出 ax+ny=gcd(a,n) 的解 x0
在将 (x0,y0) 乘上 b/gcd(a,n) ，其中的 x就是我们要的解
设 ans=x0*(b/gcd(a,n)) ，s=n/gcd(a,n) ，那么同余方程 ax≡b(mod n) 的最小正整数解就是 (ans%s+s)%s

#include<bits/stdc++.h>
using namespace std;

//找到一组解x,y,使得ax+by=gcd(a,b)并返还gcd(a,b)
int exgcd(int a,int b,int &x,int &y){//注意&,否则最后就取不到要求的x,y了
    if(b==0){
        x=1;
        y=0;
        return a;
    }
	int r=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
    y=t-a/b*y;
    return r;
}

int linear_equation(int a,int b,int n,int &x,int &y){//同样也要用&关联
	int d=exgcd(a,n,x,y);//是先求gcd(a,n)
	if(b%d)
	return 0;
    int ans=x*b/d;
    int s=n/d;
	ans=(x%s+s)%s;//放止出现负数(取正的最小整数解)
	return ans;
}

signed main()
{
    int a,b,n,x,y;
    cin>>a>>b>>n;
    int tot=linear_equation(a,b,n,x,y);//注意传入的顺序
    if(tot){//求出一组整数解即可
        cout<<"YES"<<endl;
        cout<<tot<<endl;
    }
    else cout<<"NO"<<endl;
    return 0;
}

欧拉函数和欧拉定理

欧拉函数

欧拉函数定义

表示小于等于 n 且与 n 互质的数的个数的一类数成为欧拉函数，记作 φ(n)

例：φ(8)=4 ，因为与 8 互质且小于等于 8 的正整数有 4 个，它们是：1 ，3 ，5 ，7

欧拉函数性质

欧拉函数是积性函数——若 m,n 互质，φ(mn)=φ(m)*φ(n)
当 n 为奇数时，φ(2n)=φ(n) ，上述性质就可以证明

欧拉函数引理

引理一

如果 n 为某一个素数 p ，则 φ(p)=p-1

因为 p 内的数和 p 公因数不为1的只有本身，其他数均和 p 互质

引理二

如果 n 为某一个素数 p 的幂次，那么 φ(p^a)=(p-1)*p^(a-1)

因为比 p^a 小的数有 p^a-1 个，那么有 p^(a-1)-1 个数能被 p 所整除，把 1~p^a-1 的 p 的倍数和本身都筛去，所以 φ§=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)

引理三

如果 n 为任意两个互质数 a 和 b 的积，那么 φ(a*b)=φ(a)*φ(b)

因为比 a*b 小的数有 a*b-1 个，只有那些既满足 a 与其互质且既满足 b 与其互质的数满足条件。根据乘法原理，这样的数可以互相组合，那么就有 φ(a)*φ(b)个

引理四

设 n=(p1^a1)*(p2^a2)*……*(pk^ak) (为n的分解式) ，那么 φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)

分解时，优先满足小的因子，多余相同的因子累积挂幂

因为各个分解完的 p1、p2、……、pk 均为素数，所以它们均为互质的

每次再刨去它们本身乘起来，剩下的运用容斥原理，再根据引理二和引理三就可以得出

注意：每种质因数只能有一个。比如 12=2*2*3 那么 φ(12)=12*(1-1/2)*(1-1/3)=4

求欧拉函数模板

方法有很多，这里总结两个效率比较高也常用的模板

利用引理四

问题：求一个整数 n 的欧拉函数

时间复杂度：O(sqrt(n))

//因为欧拉函数可能为质数形式，防止爆零注意数据的范围
ll eular(ll n){
    ll ret=1,i;
    for(i=2;i*i<=n;i++)
        if(n%i==0){
            n/=i,ret*=i-1;
            while(n%i==0)
                n/=i,ret*=i;
        }
    if(n>1)
        ret*=n-1;
    return ret;
}

利用欧拉线性筛法

问题：求 1~n 内的素数和所有数的欧拉函数

时间复杂度：O(n)

//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;

int n;
int tot;//寄存指针
int phi[maxn];//保存各个数字的欧拉函数 
int prime[maxn];//按顺序保存素数
bool mark[maxn];//判断是否是素数

void get_phi(){
    phi[1]=1;//特例
    for(int i=2;i<=n;i++){//相当于分解质因数的逆过程
        if(!mark[i]){
            prime[++tot]=i;//从1开始存
            phi[i]=i-1;
        }
        for(int j=1;j<=tot;j++){
            if(i*prime[j]>n)break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0){//判断prime[j]是否为i的约数
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else{//prime[j]-1就是phi[prime[j]],利用了欧拉函数的积性
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}

signed main()
{
    while(cin>>n){
        tot=0;
        get_phi();
        for(int i=1;i<=tot;i++)//输出素数
        cout<<prime[i]<<" ";
        cout<<endl;
        for(int i=1;i<=n;i++)//输出每个数的欧拉函数
        cout<<phi[i]<<" ";
        cout<<endl;
    }
    return 0;
}

利用埃氏筛法

问题：求 1~n 内所有数的欧拉函数

时间复杂度：O(nlognlogn)

//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;

int n;
int phi[maxn];//保存各个数字的欧拉函数 


//得开一个phi数组用来存储φ(i)
void get_phi(int n)
{
    for (int i=1;i<=n;i++)phi[i]=i;
    for (int i=2;i<=n;i++)
    {
        if (phi[i]==i)//这代表i是质数
        {
            for (int j=i;j<=n;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉
            }
        }
    }
}

signed main()
{
    while(cin>>n){
        get_phi(n);
        for(int i=1;i<=n;i++)//输出每个数的欧拉函数
        cout<<phi[i]<<" ";
        cout<<endl;
    }
    return 0;
}

欧拉定理

若正整数 a ，n 互质，则 a^φ(n)≡1(mod n) 。其中 φ(n) 是欧拉函数

费马小定理

若 p 是素数，a 是正整数且不能被 p 整除，则 a^(p-1)≡1(%p)
推论：若 p 是素数，a 是正整数且不能被 p 整除，则 a^p≡a(%p)

欧拉定理推论

若正整数 a ，n互质，则对于任意正整数 b 有 a^b≡a^b%φ(n)(mod n)

逆元

定义：也称模乘法的逆，当完全剩余系中两个元素 a ，b满足 ab==1 时称 a ，b 互为乘法的逆。记为：a=b^-1，b=a^-1，简单来说，当 a*b≡1(mod m) 时， a ，b 互为逆元

应用：当题目要求对结果求m的模，且当过程需要计算 a/b时，需要对 a/b 取模，即 (a/b)mod m ，有时 a/b 过于大会出现爆精度的情况，所以需要变除法为乘法：设 c 是 b 的逆元，则 b*c≡1(mod m) ，故 (a/b)mod m=(a/b)*1 mod m=(a/b)*b*c mod m=(a*c)mod m

即 (a/b)mod m=(a mod m*c mod m)mod m

实现

求法一：用费马小定理	求法二：用扩展欧几里得算法
`p` 必须是质数	`p` 可以不是质数
`a` 是不能被质数 `p` 整除的正整数	对于不完全为 0 的非负整数 `a` ，`b`

模板

参考博客求法有很多种，这里只给出两种正经做法的模板

费马小定理求逆元

方法：由 a^(p-1)≡1(mod p) 可得 a*a^p-2≡1(mod p)，所以 a^p-2 是 a 的逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;//根据题目来确定

ll quick_pow(ll a,ll b){//矩阵快速幂
    ll res=1,base=a%mod;
    while(b){
        if(b&1)
            res=(base*res)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return res;
}

ll inv(ll a){
    return quick_pow(a,mod-2);//求逆元
}

signed main()
{
    ll a,b;
    cout<<inv(a)*b%mod<<endl;
    return 0;
}

扩展欧几里得算法求逆元

方法：由逆元定义可知，求 a 模 m 的逆元 x ，即为求解同余方程 ax≡1(mod m) ，将方程转化为 ax-my=1 ，然后套用求不定方程的模板求出关于 gcd(a,m)的解(x0,y0) ，然后检查 gcd(a,m) 是否为 1 ，若不是说明逆元不存在，否则借助 x0 求出在 [1,m-1] 内的 x 就是所要的逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,y,x);
    y=y-x*(a/b);
    return gcd;
}

ll inv(ll a){
    ll x,y;
    exgcd(a,mod,x,y);
    x=(x%mod+mod)%mod;//其实就是最小正整数解
    return x;
}

signed main()
{
    ll a,b;
    cout<<inv(a)*b%mod<<endl;
    return 0;
}

威尔逊定理

参考博客由于 (p-1)! 较大，实际应用不是很广泛

当且仅当 p 是质数时：(p−1)!≡−1(mod p)

卢卡斯定理

参考博客

中国剩余定理以及扩展定理

中国剩余定理

事例

有物不知其数，三三数之剩二。五五数之剩三，七七数之剩二。即 x%3=2,x%5=3,x%7=2 ，需要求出 x

做法：

分别从 3 和 5 , 3 和 7 , 5 和 7 的公倍数中找出被 7 除余 1 的最小数 15 ，被 5 除余 1 的最小数 21 ，除 3 余 1 的最小数 70
用 15 乘以 2（ 2 为最终结果除以 7 的余数），用 21 乘以 3（ 3 为最终结果除以 5 的余数），同理用 70 乘以 2（ 2 为最终结果除以 3 的余数），然后把三个乘积相加得到和 233
用 233 除以 3 、5 、7 的最小公倍数 105 ，得到余数 23 ，这个余数 23 就是符合条件的最小数

模板

模板题：一个正整数 K ，给出 K mod 一些质数的结果，求符合条件的最小的 K 。第1行：1 个数 N 表示后面输入的质数及模的数量。第 2-N+1 行，每行 2 个数 P 和 M ，中间用空格分隔，P 是质数，M 是 K%P 的结果。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=15;

ll n;
ll m[maxn],a[maxn];//m[]为除数，a[]为余数

//ti同余式的求解可以用拓展欧几里得求
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){ x=1; y=0; return;}
    exgcd(b,a%b,x,y);
    ll tp=x;
    x=y; y=tp-a/b*y;
}

ll china(){
    ll ans=0,lcm=1,x,y;//lcm为最小公倍数，ans用来累加求解x
    for(ll i=1;i<=n;++i) 
    lcm*=m[i];
    for(ll i=1;i<=n;++i){
        ll tot=lcm/m[i];
        exgcd(tot,m[i],x,y);
        x=(x%m[i]+m[i])%m[i];//x要为最小非负整数解
        ans=(ans+tot*x*a[i])%lcm;//累加
    }
    return (ans+lcm)%lcm;//保证整体还是最小整数解
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;//存入几组数据
    for(ll i=1;i<=n;i++)
    cin>>m[i]>>a[i];//从1开始存储
    cout<<china()<<endl;
    return 0;
}

扩展中国剩余定理

扩展中国剩余定理和中国剩余定理的区别在于除数不在互质，使用范围更加广泛

模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=15;

int n;
ll m[maxn],a[maxn];//m[]为除数，a[]为余数

ll quick_mul(ll a,ll b,ll mod){//快速乘
    ll ans=0;
    while(b>0){
        if(b&1)ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}

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

ll excrt(){
    ll x,y,k;
    ll M=m[1],ans=a[1];
    for(int i=2;i<=n;i++)
    {
        ll tot=M,b=m[i],c=(a[i]-ans%b+b)%b;
        ll d=exgcd(tot,b,x,y),bg=b/d;
        if(c%d!=0) return -1;//不存在返还-1 
        
        x=quick_mul(x,c/d,bg);
        ans+=x*M;//更新答案
        M*=bg;
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)//从1开始存储
    cin>>m[i]>>a[i];
    cout<<excrt()<<endl;
    return 0;
}

快速乘、快速幂及矩阵快速幂

这篇博客是目前见过讲的最全最细的，原理三者都差不多看这篇

快速乘

ll quick_mul(ll a,ll b,ll mod){
    ll ans=0,base=a;
    while(b>0){
        if(b&1)ans=(ans+base)%mod;
        base=(base+base)%mod;
        b>>=1;
    }
    return ans;
}

快速幂

ll quick_pow(int a, int b, ll mod) {
    ll ans=1,base=a;
    while(b){
        if(b&1)ans=ans*base%mod;
   		base=base*base%mod;
        b>>= 1;
    }
    return ans;
}

快速幂和快速乘的本质都是将十进制的运算规则转换为二进制运算规则

这里的 base 是将 a 内容复制供函数修改使用，实际上直接在 a 本身修改就行反正函数没指针是深复制

矩阵快速幂

参考博客矩阵快速幂就是把快速幂中的乘法改用矩阵乘法从而起到加速的作用

矩阵快速幂的核心是如何将找到的矩阵乘法需要的矩阵递推式构造出来，这里给出几个常用的

矩阵快速幂需要算的地方时那个带幂次的矩阵，最后运算手推看看需要输出哪部分

因为是矩阵自身不断递推计算且都是正方形，所以 x 记录基础递推矩阵， y 记录每次计算出的矩阵结果，最后记录的就是矩阵自身结果

const int maxn=15;//矩阵最大边长
const int mod=1e7;//模运算的取模

int len;//正方形矩阵边的长度

struct node{
	int mat[maxn][maxn];//定义矩阵 
}x,y;

node mul(node x,node y){//矩阵乘法（取模）
	node tmp;
	for(int i=0;i<len;i++){
		for(int j=0;j<len;j++){
			tmp.mat[i][j]=0;
			for(int k=0;k<len;k++){
				tmp.mat[i][j]+=(x.mat[i][k]*y.mat[k][j])%mod;
			}
			tmp.mat[i][j]=tmp.mat[i][j]%mod;
		}
	}
	return tmp;
} 

node matpow(node x,node y,int num){//矩阵快速幂 
	while(num){
		if(num&1){
			y=mul(y,x);
		}
		x=mul(x,x);
		num=num>>1;
	}
	return y;
}

signed main(){
    //len先定义好
    init();//初始化基础矩阵x和记录结果的矩阵为单位矩阵
}

模板题：求第 n 项的斐波那契数对 10000 求余

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=2;//矩阵最大边长
const int mod=1e4;//模运算的取模

int len;//正方形矩阵边的长度

struct node{
	int mat[maxn][maxn];//定义矩阵 
}x,y;//x是基础递推矩阵,y矩阵记录结果

node mul(node x,node y){//矩阵乘法 
	node tmp;
	for(int i=0;i<len;i++){
		for(int j=0;j<len;j++){
			tmp.mat[i][j]=0;
			for(int k=0;k<len;k++){
				tmp.mat[i][j]+=(x.mat[i][k]*y.mat[k][j])%mod;
			}
			tmp.mat[i][j]=tmp.mat[i][j]%mod;
		}
	}
	return tmp;
} 

node matpow(node x,node y,int num){//矩阵快速幂 
	while(num){
		if(num&1){
			y=mul(y,x);
		}
		x=mul(x,x);
		num=num>>1;
	}
	return y;
}

void init(){
    //递推的基础矩阵
    x.mat[0][0]=1;
    x.mat[0][1]=1;
    x.mat[1][0]=1;
    x.mat[1][1]=0;
    //记录结果的矩阵
    y.mat[0][0]=y.mat[1][1]=1;
    y.mat[0][1]=y.mat[1][0]=0;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    len=2;
    while(cin>>n&&n!=-1){
        //两个特判
        if(n==0){//-1次幂算不了
            cout<<0<<endl;
            continue;
        }
        if(n==1){//0次幂没必要算
            cout<<1<<endl;
            continue;
        }
        init();
        node tot=matpow(x,y,n-1);
        cout<<tot.mat[0][0]%mod<<endl;
    }
    //system("pause");
    return 0;
}