同余式

1. 算法分析

1.1 同余式常用定理

1.1.1 欧拉公式/费马小定理

欧拉公式:
    若gcd(a, n) = 1, 则a^φ(n) = 1 (mod n)
费马小定理
    若p是质数，则a^p = a(mod p) => a^p-1 = 1(mod p)
欧拉公式/费马小定理常用来化简式子，通过a^φ(n) = 1 (mod n)的关系，把式子的一部分转换为1

1.1.2 威尔逊公式

1. p为素数 <=> (p - 1)! ≡ -1(mod p)
2. p为素数 <=> (p - 1)! ≡ (p - 1) (mod p)
3. p为素数 <=> p | ((p-1)! + 1)

因此，当发现算式有 (p-1)! 时，可以考虑威尔逊定理的使用

1.1.3 扩展欧几里得

对于方程:

特殊地，ax+by=1有解 <=> gcd(a, b)=1
输入a,b，使用扩展欧几里得算法可以求出ax + by = gcd(a, b)的一个解为(x0, y0),那么ax + by = gcd(a, b)的通解为:

\begin{cases}
x = x0+(b/gcd)*t \\
y = y0-(a/gcd)*t 
\end{cases}

ax + by=m的通解为:

\begin{cases}
x = x0*m/gcd+(b/gcd)*t \\
y = y0*m/gcd-(a/gcd)*t \\
(这里的x0、y0是ax+by=gcd求出来的)
\end{cases}

ax+by=gcd(a, b)和ax+by=m的通解的周期都是b/gcd，不会变

对ax+by=m进行变形，ax ≡ m (mod b)
则x∈[0, b)，解的数目为gcd(a, b)个，第一个解在[0, b/gcd),第二个解在[b/gcd, 2b/gcd),…

1.2 乘法逆元

1. 扩展欧几里得
   ax ≡ 1(mod p) <=> ax + py ≡ 1(mod p)，因此可以使用扩展欧几里得求ax + py ≡ 1(mod p)解逆元，求出来的逆元就是x

2. 费马小定理
   a^p-1 ≡ 1(mod p) <=> a的逆元为a^p-2(mod p),当且仅当p为素数情况

3. 线性求逆元
   首先有
   1^-1≡1(mod p)
   设
   p=k * i + r, r < i, 1 < i < p
   两边同时mod p，有
   k * i + r ≡0 (mod p)
   两边同时乘上i^-1 * r^-1，得到
   k* r^-1+ i^-1≡ 0(mod p)
   移项
   i^-1≡-k * r^-1 (mod p)
   i^-1≡-⌊P/i⌋ * (p mod i)^-1 (mod p)
   以inv(i)表示i在mod p下的逆元,则有递推公式:
   inv[i]= -(p/i) * inv[p % i]

1.3 求解同余式

1.3.1 求解一次同余式

求解一次同余式 ax ≡ 1(mod p), 直接乘法逆元求解

1.3.2 求解高次同余式

求解高次同余式 a^x ≡ 1(mod p), 使用baby Step，Giant Step算法求解

1.4 中国剩余定理

1. 原始版中国剩余定理

假设整数m1,m2, … ,mn两两互质，则对任意的整数：a1,a2, … ,an，方程组 (S) 有解，并且通解可以用如下方式构造得到：

\begin{cases}
x ≡ a1 (mod m1) \\
x ≡ a2 (mod m2) \\ 
x ≡ a3 (mod m3) \\
x ≡ a4 (mod m4)
\end{cases}

有解的判定条件，并用构造法给出了在有解情况下解的具体形式。
中国剩余定理说明：假设整数m1,m2, … ,mn两两互质，则对任意的整数：a1,a2, … ,an，方程组 有解，并且通解可以用如下方式构造得到：
$$x=\sum _{i=1}^{n}ai\ast ti\ast Mi+kM$$
在mod M的意义下:
$$x=(\sum _{i=1}^{n}ai\ast ti\ast Mi)modM$$

2. 拓展版中国剩余定理

普通的中国剩余定理要求所有的mi互素， 那么如果不互素呢，求解同余方程组方法如下：
①这种情况采用两两合并的思想，假设要合并如下两个方程:
x = a1 + m1x2
x = a2 + m2x2
那么得到: a1+ m1x1 = a2 + m2x2 => m1x1 + m2x2 = a2 - a1

②使用扩展欧几里得算法得到一个最小的x1，从而得出最小的x使他满足:
x = a1 + m1x1 = a2 + m2x2
这样得到的是x的一个特解x’,当然也是最小正整数解

③所以x的通解一定是x’加上lcm(m1,m2)*k，这样才能保证x模m1和m2的余数是a1和a2.由此，我们把这个x’当作新方程的余数，把lcm(m1, m2)当作新的方程的模数
合并完成：x ≡ x’ (mod lcm(m1, m2))

1.5 思维同余性质

• 同余的考题很多结合距离可以回头的概念，比如自西向东一旦到了尽头那么又是自西向东，这样会产生同余的情况
• 还有很多考察欧拉公式等

2.板子

2.1 同余式常用定理

扩展欧几里得算法

// 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {   // b==0时，x=1， y=0
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); // b != 0时，gcd(a, b) = gcd(b, a % b), x = x， y = y - a/b * x;
    y -= a / b * x;
    return d;
}

2.2 乘法逆元

1. 扩展欧几里得求逆元

// 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {  // b==0时，x=1， y=0
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x); // b != 0时，gcd(a, b) = gcd(b, a % b), x = x， y = y - a/b * x;
    y -= a / b * x;
    return d;
}

LL getInv(LL a, LL mod) {  //求a在mod下的逆元，不存在逆元返回-1
    LL x, y;
    LL d = exgcd(a, mod, x, y);
    return d == 1 ? (x % mod + mod) % mod: -1;
}

2. 费马小定理求逆元

LL qmi(LL a, LL k, LL p)   {
    LL res = 1 % p;  // res记录答案, 模上p是为了防止k为0，p为1的特殊情况
    while(k) { // 只要还有剩下位数
        if (k & 1) res = (LL)res * a % p;  // 判断最后一位是否为1，如果为1就乘上a，模上p, 乘法时可能爆int，所以变成long long
        k >>= 1;  // 右移一位
        a = (LL) a * a % p;  // 当前a等于上一次的a平方，取模，平方时可能爆int，所以变成long long
    }
    return res;
}

LL get_inv(LL a, LL p) {
    return qmi(a, p - 2, p);
}

3. 线性求逆元

打表

/ inv[i]=-(mod/i)*inv[i%mod]
LL inv[mod+5];
void getInv(LL mod) {
    inv[1]=1;
    for(int i=2;i<mod;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

递归

LL inv(LL i) {
    if(i==1)return 1;
    return (mod-mod/i)*inv(mod%i)%mod;
}

2.3 求解同余式

1. 求解一次同余式
   直接逆元，见2.2

2. 求解高次同余式

// 求解a^x=b(mod p),返回值为x
int baby_step_giant_step(int a, int b, int p) {
    map<int, int> hash; 
    hash.clear();
    b %= p;
    int t = (int)sqrt(p) + 1;
    for (int j = 0; j < t; ++j) {
        int val = (LL)b * qmi(a, j, p) % p;
        hash[val] = j;
    }
    a = qmi(a, t, p);
    if (a == 0) return b == 0? 1: -1;
    for (int i = 0; i <= t; ++i) {
        int val = qmi(a, i, p);
        int j = hash.find(val) == hash.end()? -1: hash[val];
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}}

2.4 中国剩余定理

1. 原始版中国剩余定理–模数互质

// 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {  // b==0时，x=1， y=0
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); // b != 0时，gcd(a, b) = gcd(b, a % b), x = x， y = y - a/b * x;
    y -= a / b * x;
    return d;
}


//a, m --- 第i个方程表示x ≡ ai(mod mi)
// n---- 方程个数
int CRT( int a[], int m[], int n ) {  //x ≡ ai(mod mi)
    int M = 1;
    for(int i=0;i<n;++i) M *= m[i];
    int ret = 0;
    for(int i=0;i<n;++i) {
        int x,y;
        int tm = M/m[i];
        exgcd(tm,m[i],x,y);//调用外部函数：拓展欧几里得
        ret = (ret+tm*x*a[i])%M;
    }
    return (ret+M)%M;
}

2. 扩展版中国剩余定理–模数不互质

// 扩展欧几里得算法
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int n;
    cin >> n;
    bool ans = true;  // 判断是否有答案
    LL a1, m1;
    cin >> a1 >> m1;  // x≡mi(mod ai)
    for (int i = 0; i < n - 1; ++i) {
        LL a2, m2;
        scanf("%lld %lld", &a2, &m2);
        LL k1 ,k2;
        LL d = exgcd(a1, a2, k1, k2);  // 扩张欧几里得算法得到k1，k2,d
        if ((m2 - m1) % d) {  // 如果能够整除，裴属等式无解，则题目无解
            ans = false;
            break;
        }
        k1 = k1 * (m2 - m1) / d;  // 计算k1的实际值(扩张欧几里得算出的是ax+by=gcd(a, b)情况下的k1)
        LL t = a2 / d;  // 得到k①=k1+k*a2/d中的斜率a2/d
        k1 = (k1 % t + t) % t;  // 取得正整数范围内的最小的k1
        m1 = k1 * a1 + m1;  // 得到x通解x=ka+m1
        a1 = abs(a1 * a2 / d);  // 得到通解形式下的斜率a
    }
    if (ans) {
        cout << (m1 % a1 + a1) % a1 << endl;  // 有解输出满足x≡mi(mod ai)的最小x
    }
    else cout << -1 << endl;  // 无解输出-1
    return 0;
}

3. 例题

3.1 同余式常用定理

hdu2973-YAPTCHA
题意： 计算$ s_n = \sum_{k=1}^n[\frac{(3k + 6)! + 1}{3k + 7} - [\frac{(3k+6)!}{3k+7} ] ]$
给定1e6个测试样例，每个测试样例给一个n~1e6,求sn
题解：
题目的意思就是求题目中的Sn式子的值，出现(p-1)!的形式，考虑威尔逊定理
其中[x]表示不大于x的最大整数。
威尔逊定理：当且仅当p为素数时，( p − 1)!≡−1(mod p)。
分析：如果3k+7为质数，根据定理，那么[((3k+6)! + 1)/(3k+7) - [(3k+6)!/(3k+7)]]相减就为1，否则这两个数差为0。
令p=3*k+7
1.若p是素数, ( (p-1)!+1 )/p是个整数，设为x，则(p-1)!/p比这个整数小一点点，取整后是x-1，
则[ ( (p-1)!+1 )/p - [(p-1)!/p] ]=1;
2.若p是合数，(p-1)!/p是个整数，设为y，则( (p-1)!+1 )/p比这个整数大一点点，取整后还是y，
则[ ( (p-1)!+1 )/p - [(p-1)!/p] ]=0；
代码：

#include <iostream>

using namespace std;

int const N = 1e6;
int prime[N * 3 + 7], st[N * 3 + 7], s[N * 3 + 7];

// 利用线性筛法来得到素数表
void get_prime(int n) {
    int cnt = 0;
    for (int i = 2; i <= n * 3 + 7; ++i) {
        if (!st[i])
            prime[cnt++] = i;
        for (int j = 0; prime[j] <= (n * 3 + 7) / i; ++j) {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;      
        }                
    }
    for (int i = 2; i <= n; ++i) {  // 前缀和s[i]记录到值为i时有多少个素数
        if (!st[3 * i + 7]) s[i] = s[i - 1] + 1;
        else s[i] = s[i - 1];
    }
}

int main() {
    int T;  // 输入样例数目
    cin >> T;   
    get_prime(N);  // 利用线性筛素数打印素数表
    while(T--) {
        int n;  // 读入数组
        cin >> n;
        printf("%d\n", s[n]);  // 打印对应的素数个数
    }
    
    return 0;
}

3.2 求解同余式

acwing203同余方程
题意： 求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。
题解： 注意b不一定是素数
代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int a, b;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x); // b != 0时，gcd(a, b) = gcd(b, a % b), x = x， y = y - a/b * x;
    y -= a / b * x;
    return d;
}

LL getInv(LL a,LL mod) {
    LL x, y;
    LL d = exgcd(a, mod, x, y);
    return d == 1 ? (x % mod + mod) % mod: -1;
}

int main() {
    cin >> a >> b;
    cout << getInv(a, b);
    return 0;
}

acwing224计算器
题意： 计算快速幂、一次线性同余、高次同余方程
题解： 模板
代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int t, type, y, z, p;

LL qmi(LL a, LL k, LL p) {
    LL res = 1 % p;
    while (k) {
        if (k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

// 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x); // b != 0时，gcd(a, b) = gcd(b, a % b), x = x， y = y - a/b * x;
    y -= a / b * x;
    return d;
}

LL getInv(LL a,LL mod) {
    LL x, y;
    LL d = exgcd(a, mod, x, y);
    return d == 1 ? (x % mod + mod) % mod: -1;
}

int baby_step_giant_step(int a, int b, int p) {
    map<int, int> hash; 
    hash.clear();
    b %= p;
    int t = (int)sqrt(p) + 1;
    for (int j = 0; j < t; ++j) {
        int val = (LL)b * qmi(a, j, p) % p;
        hash[val] = j;
    }
    a = qmi(a, t, p);
    if (a == 0) return b == 0? 1: -1;
    for (int i = 0; i <= t; ++i) {
        int val = qmi(a, i, p);
        int j = hash.find(val) == hash.end()? -1: hash[val];
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}

int main() {
    cin >> t >> type;
    while (t--) {
        cin >> y >> z >> p;
        if (type == 1) {
            cout << qmi(y, z, p) << endl;
        }
        else if (type == 2) {
            LL res = getInv(y, p);
            if (res == -1) {
                cout << "Orz, I cannot find x!\n";
                continue;
            }
            else cout << (z * res % p + p ) % p << endl;
        }
        else{
            LL res = baby_step_giant_step(y, z, p);
            if (res == -1) {
                cout << "Orz, I cannot find x!\n";
                continue;
            }
            else cout << res << endl;
        }
    }
    return 0;
}

acwing202最幸运的数字

3.3 中国剩余定理

acwing1298曹冲养猪
题意： 有X头猪，当建立ai个猪圈，有bi头猪没有去处。输入n个条件，每个条件为ai,bi，求出X。n~10, ai、bi~1e6， ai*bi <= 1e18
题解： crt模板
代码：

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

typedef long long LL;

// 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x); // b != 0时，gcd(a, b) = gcd(b, a % b), x = x， y = y - a/b * x;
    y -= a / b * x;
    return d;
}

//a, m --- 第i个方程表示x ≡ ai(mod mi)
// n---- 方程个数 
LL CRT( LL a[], LL m[], LL n ) {
    LL M = 1;
    for(LL i=0;i<n;++i) M *= m[i];
    LL ret = 0;
    for(LL i=0;i<n;++i) {
        LL x,y;
        LL tm = M/m[i];
        exgcd(tm,m[i],x,y);//调用外部函数：拓展欧几里得
        ret = (ret+tm*x*a[i])%M;
    }
    return (ret+M)%M;
}
 
int main() {
    int n;
    cin >> n;
    LL a[11], m[11];
    for (int i = 0; i < n; ++i) {
        cin >> m[i] >> a[i];
    }
    cout << CRT(a, m, n) << endl;
    return 0;
}

acwing204表达整数的奇怪方式
题意： 给定 2n 个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数 x，满足∀i∈[1,n],x≡mi(mod ai)。
题解：
对应任意的a1,m1,a2,m2
如果x≡m1(mod a1), x≡m2(mod a2)
则x = k1a1+m1, x = k2a2+m2
则有k1a1+m1=k2a2+m2,则有k1a1-k2a2=m2-m1，这个二元一次方程的解集为k①=k1+k * a2/d,k②=k2+k * a1/d
把解集带入第三行，有x = ka1a2/d+k1a1+m1=ka+m1 (其中m1 = k1a1+m1, a = a2 * a1 / d)
因此，求解本题时，可以先借助扩展欧几里得算法求出k1和k2
从而计算出最小的k①，得到x的通解x=ka+m1,取最小的即可
本题求满足x≡7(mod 8), x≡9(mod 11)的最小x
代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

// 扩展欧几里得算法
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int n;
    cin >> n;
    bool ans = true;  // 判断是否有答案
    LL a1, m1;
    cin >> a1 >> m1;  // x≡mi(mod ai)
    for (int i = 0; i < n - 1; ++i) {
        LL a2, m2;
        scanf("%lld %lld", &a2, &m2);
        LL k1 ,k2;
        LL d = exgcd(a1, a2, k1, k2);  // 扩张欧几里得算法得到k1，k2,d
        if ((m2 - m1) % d) {
            ans = false;
            break;
        }
        k1 = k1 * (m2 - m1) / d;  // 计算k1的实际值(扩张欧几里得算出的是ax+by=gcd(a, b)情况下的k1)
        LL t = a2 / d;  // 得到k①=k1+k*a2/d中的斜率a2/d
        k1 = (k1 % t + t) % t;  // 取得正整数范围内的最小的k1
        m1 = k1 * a1 + m1;  // 得到x通解x=ka+m1
        a1 = abs(a1 * a2 / d);  // 得到通解形式下的斜率a
    }
    if (ans) {
        cout << (m1 % a1 + a1) % a1 << endl;
    }
    else cout << -1 << endl;  // 无解输出-1
    return 0;
}

3.4 思维同余性质

acwing222青蛙的约会
题意： 两只青蛙，初始位置分别在x,y。两只青蛙每次跳的距离分别为m, n,路是一个环（跳到头再往前跳相当于从开始跳），总长为l,求要使两只青蛙能够相遇，最少两只青蛙都需要跳几次。x,y,m,n,l~2e9
题解： 设初始位置分别为a,b,每次两只青蛙跳的步数为m和n，因此两只青蛙能够遇到就要满足：
(m - n) * x - y * l = b - a
所以就是要去寻找式子中的x，然后考虑使用扩展欧几里得求参数即可
同时要注意，求出来的x可能是负数，因此需要去寻找该剩余内其他的最小的正数
而x的通解形式为:x=x0 * m/gcd+k * (b/d)，通过这个方式求得正整数解
代码：

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

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
 
int main() {
    long long x, y, m, n, l, a, b;
    cin >> a >> b >> m >> n >> l;
    long long d = exgcd(m - n, l, x, y);
    if ((b - a) % d) printf("Impossible\n");
    else  {
        x *= (b - a) /d ;
        long long t = abs(l / d);
        cout << (x % t + t) % t << endl;
    }
    return 0;
}