零，前言：

学 chty_sqy 开个数论集合

学 OI 的时候一看数论就头大，现在该还了 T_T

建议推导和证明不熟或不会的同学动手推导

下面知识点的详情（推导和证明）都可以在我的博客里找到，URL 太长就不贴了

而且公式看上去不太清楚，学习的同学请仔细阅读

以前数论怎么都学不会，主要还是浮躁，不仔细看，没有动手 orz

一，GCD（欧几里德算法）：

两个数 $a$ 和 $b$ 的最大公因数被称为 $gcd(a, b)$

求 gcd 通常用欧几里得算法

原理： $gcd(a, b) = gcd(b, a \% b)$

代码：

1	int gcd(int a,int b){ return b ? gcd(b,a%b) : a;}

二，EXGCD（扩展欧几里德算法）：

数论守门员

有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行。

扩展欧几里得算法研究的是形如 $a \cdot x + b \cdot y = c$ 的丢番图方程的解

方程有解当且仅当 $gcd(a, b)|c$

原理： $a \cdot x_1 + b \cdot y_1 = gcd(a, b), b \cdot x_2 + (a \% b) \cdot y2 = gcd(b, a \% b), gcd(a, b) = gcd(b, a \% b) \Rightarrow x_1 = y_2, y_1 = x_2 - \lfloor \frac{a}{b} \rfloor \cdot y_2$

代码：

void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int z=x;
    x=y,y=(z-a/b*y);
}

例题：

洛谷4549 裴蜀定理

洛谷1516 青蛙的约会

洛谷3951 小凯的疑惑

洛谷1082 同余方程

三，CRT（中国剩余定理）：

今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何？

一次同余方程组是指形如 $x \equiv a_i \mod m_i \quad (i = 1, 2, …, k)$ 的同余方程构成的组

中国剩余定理的主要用途是解一次同余方程组，其中 $m_1, m_2, ..., m_k$ 互质

原理：构造一个解 $x = \sum a_i \cdot \frac{M}{m_i} \cdot t_i$ ，其中 $t_i$ 为同余方程 $\frac{M}{m_i} \cdot t_i \equiv 1 \mod m_i$ 的最小正整数解， $t_i$ 可用 exgcd 求出

代码：

（其中 LL 是 long long ，qcm 是快速乘）

LL crt(){
    LL bwl=0;
    for(int i=1;i<=k;++i){
        LL x,y;
        exgcd(M/m[i],m[i],x,y);
        if(x<0)  x=x%m[i]+m[i];
        bwl=(bwl+qcm(qcm(a[i],M/m[i]),x))%M;
    }
    return (bwl+M)%M;
}

例题：

洛谷3868 猜数字

四，EXCRT（扩展中国剩余定理）：

扩展中国剩余定理的主要用途是解一次同余方程组，其中 $m_1, m_2, ..., m_k$ 不一定互质

原理：由前 $k - 1$ 个方程组成的方程组的通解 $x + t \cdot M$ ，令 $x + t \cdot M \equiv a_k \mod m_k$ 构造出前 $k$ 个方程的解， $t$ 可用 exgcd 求出

若 $x + t \cdot M \equiv a_k \mod m_k$ 无解，则整个同余方程组无解

代码：

（其中 LL 是 long long，qcm 是快速乘，三个参数分别为两个乘数和模数）

LL excrt(){
    LL M=m[1],ans=a[1];
    for(int i=2;i<=k;++i){
        LL x,y;
        LL d=gcd(M,m[i]);
        LL c=(a[i]-ans%m[i]+m[i])%m[i];
        if(c%d)  return -1;
        exgcd(M,m[i],x,y);
        x=qcm(x,c/d,m[i]/d);
        ans+=qcm(x,M,M*m[i]);
        M*=m[i]/d;
        ans=(ans%M+M)%M;
    }
    return ans;
}

例题：

洛谷4777 扩展中国剩余定理

五，BSGS（大步小步算法）

BSGS 一般用于求解离散对数，即求关于 $x$ 的方程 $a^x \equiv b \mod p$ 的最小整数解，其中要求 $gcd(a, p) = 1$

做法很简单，不妨设 $x = rm - q$

那么得到 $a^{rm} \equiv ba^q \mod p$

由于 $gcd(a, p) = 1$ ，所以 $a^{p - 1} \equiv 1 \mod p$ ，所以 $0 \leq x < p - 1$

那么有 $0 \leq q < m, 1 \leq r < \lceil \frac{p - 1}{m} \rceil$

我们就可以先枚举 $q$ ，把 $ba^q$ 的值放到 map 或者哈希里，然后再枚举 $r$

如果发现 $a^{rm} \equiv ba^q \mod p$ ，那就找到解了，找不到就是无解

显然当 $m = \sqrt p$ 时时间复杂度最优，为 $O(\sqrt p)$

代码：

ll bsgs(ll x,ll y,ll z){
        x%=z,y%=z;
        if(y==1)  return 0;
        if(x==0 && y==0)  return 1;
        if(x==0 && y!=0)  return -1;
        map<ll,ll> tong;
        ll w=sqrt(z)+1;
        for(ll i=0,j=y;i<w;i++,j=j*x%z)  tong[j]=i;
        ll k=qcp(x,w,z);
        for(ll i=1,j=k;i<=w+1;i++,j=j*k%z){
                if(tong.count(j))  return i*w-tong[j];
        }
        return -1;
}

六、EXBSGS（扩展大步小步算法）

EXBSGS 主要求解 $a$ 和 $p$ 不互质的情况

设 $d = gcd(a, p)$ ，并把方程写成等式形式 $a^x + kp = b$

如果 $d \nmid b$ 则方程无解，因此可以两边除 $d$ ，得到 $\frac{a}{d}a^{x - 1} + k \frac{p}{d} = \frac{b}{d}$

重复以上过程，直到 $gcd(a, \frac{p}{d}) = 1$ ，就把问题转化为普通的 BSGS 问题

只要统计一下 $a$ 被分离出的次数，最后加到得到的解里就行了

代码：

ll exbsgs(ll x,ll y,ll z){
        x%=z,y%=z;
        if(y==1)  return 0;
        ll k=0,bwl=1;
        for(ll d=gcd(x,z);d!=1;d=gcd(x,z)){
                if(y%d)  return -1;
                y/=d,z/=d;
                k++,bwl=bwl*x/d%z;
                if(y==bwl)  return k;
        }
        map<ll,ll> tong;
        ll w=sqrt(z)+1;
        for(int i=0,j=y;i<w;i++,j=j*x%z)  tong[j]=i;
        ll u=qcp(x,w,z);
        for(int i=1,j=bwl*u%z;i<=w+1;i++,j=j*u%z){
                if(tong.count(j))  return i*w-tong[j]+k;
        }
        return -1;
}