inmost's blog

inmostsama

0%

gcd及其扩展

发表于 更新于 分类于
本文字数： 3.7k 阅读时长 ≈ 7 分钟

gcd运算严格满足结合率

即有 $\gcd(a,b,c) = \gcd(\gcd(a,b),c) = \gcd(a,\gcd(b,c))$

三者求最大公约数顺序任意排列

严格证明

d=gcd(a,b)意味着d是同时能整除a,b的最大整数，g=gcd(d,c),意味着g是能同时整除d,c的最大整数
因为g能整除d,d能整除a,b，故g能整除a,b,c，即g是a,b,c的公约数
反过来，我们取a,b,c的公约数k，k定然能被其最大公约数d整除，k同时又是d,c的因数，故又能被g整除，因此g定然是a,b,c中最大的公约数（a,b的公约数是gcd(a,b)的因数的证明在下）

本质推理是素因数分解

对于两个数而言，素因数分解
$a=p_{1}^{m1} \cdot p_{2}^{m2}…p_{n}^{mk}$
$b=p_{1}^{n1} \cdot p_{2}^{n2}…p_{nk}^{mk}$
不难观察到，其最大公约数就是其素因数幂次的组合
即 最大公约数=$p_1^{\min(m_1,n_1)} p_2^{\min(m_2,n_2)} \cdots p_k^{\min(m_k,n_k)}$
根据上述式子，我们可以得到a,b的其他任意公约数均可以整除最大公约数
故不管再多的数放在一起求gcd，都是满足结合律的。（故其实也可以直接从证明看出可结合性 本质是min取的过程中不在乎顺序如何）

exgcd模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);//返回值是最大公约数
    y -= a / b * x;
    return d;
}
/*void exgcd(ll a,ll b,ll &x,ll &y){  //更简洁的求解写法
    if(b == 0) { x = 1,y = 0; return;}
    exgcd(b,a%b,y,x);           //x和y换位
    y = y- a/b*x;
}*/

返回的d即最终 $ax+by=gcd(a,b)$
即：对于任意两个不全为零的整数 $a$ 和 $b$，一定存在整数 $x$ 和 $y$，使得 $ax+by=\gcd(a,b)$ 成立。同时通过值引用，$x,y$最终的值即$x,y$的最小特解。

用处：

1.求解二元一次不定方程

用于求解形如 $ax+by=c$ 的整数解。根据裴蜀定理的推论，这个方程有解的充要条件是 $\gcd(a,b)$ 能整除 $c$。通过 exgcd 求出 $ax+by=\gcd(a,b)$ 的一组解后，将其按比例扩大，即可得到原方程的一组特解$x_0,y_0$，进而可以推导出通解。
通解：$x=x_0 + k\cdot \frac{b}{gcd(a,b)}$ ，$y=y_0 - k\cdot \frac{a}{gcd(a,b)}$
(k是任意整数)

2.求解模综合乘法逆元

当要求解 $a$ 在模 $m$ 意义下的乘法逆元 $x$ 时，等价于求解同余方程 $ax\equiv 1\pmod m$。这个同余方程可以转化为不定方程 $ax+my=1$。只要 $\gcd(a,m)=1$（即 $a$ 和 $m$ 互质），就可以直接用 exgcd 求出 $x$ 的值。
这次的exgcd的结果是在模意义下的，故其是唯一的特解，需注意实际使用中通常还需要保证取模之后的结果为正数，故+m再取余以保证正数。

费马小定理解法

求乘法逆元同时也可使用费马小定理。注意：此时要求mod必须是质数
$ax \equiv 1\pmod m$
有公式：
x即a关于模m的乘法逆元

3.求解线性同余方程组（CRT 的扩展）

在处理扩展中国剩余定理（EXCRT）时，由于模数可能不互质，普通的 CRT 无法使用。此时需要两两合并同余方程，合并的过程本质上就是求解形如 $ax+by=c$ 的线性方程，强依赖 exgcd。

CRT求解模板

能力有限，模板转载自上述链接：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
ll mod[15],yu[15],M = 1,ans;//mod[i]即为mi,yu[i]存放模后余数

void exGcd(ll a,ll b,ll &x,ll &y){   //求解 ax+by = gcd(a,b)，注意是传引用
    if(b == 0) { x = 1,y = 0; return;}         // b = 0时,a = gcd(原a,原b)
    exGcd(b,a%b,x,y);
    ll temX = x;
    x = y,y = temX - a/b * y;   //x = y1, y = x1 - a/b * y1 (x1和y1是递归下一层返回后的x和y)
}
/*void exGcd(ll a,ll b,ll &x,ll &y){  //更简洁的写法
    if(b == 0) { x = 1,y = 0; return;}
    exGcd(b,a%b,y,x);           //x和y换位
    y = y- a/b*x;
}*/
int main() {
    int n;
    cin>>n;       //方程组数
    for (int i = 1; i <= n ; ++i) {
        scanf("%ld %ld",&mod[i],&yu[i]);  //模数和余数，模数互质
        M*=mod[i];
    }
    for (int i = 1; i <= n ; ++i) {
        ll Mi = M / mod[i],inv,y; // Mi为所有模数乘积除以第i个模数，inv为Mi在模mi意义下的逆元
        exGcd(Mi, mod[i], inv, y);
        inv = (inv % mod[i]+mod[i]) % mod[i];//防止逆元求解过程中的负数出现
        ans = (ans + yu[i] * Mi * inv) % M;
    }
    cout<< (ans + M) % M;          //保证结果不出现负数
    return 0;
}

EXCRT求解模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,mod[100009],yu[100009];

//要用快速乘（龟速乘），防止爆long long
ll qMul(ll a,ll b,ll mo){
    ll an = 0;
    while(b) {
        if(b&1) an =(an+a) % mo;
        a = (a+a)%mo;
        b>>=1;
    }return an%mo;
}

//扩展欧几里得算法，返回gcd(a,b),并计算出ax+by = gcd(a,b)中的x和y
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);  //注意x和y的顺序
    y = y - a/b*x;
    return gcd;
}

int main() {
    ios::sync_with_stdio(false);//加速cin和cout
    cin>>n;
    for(int i = 1;i <= n;i++) cin>>mod[i]>>yu[i];
    ll ans = yu[1],M = mod[1] ,t,y;  //ans表示前i-1个方程式的特解（余数），M为前i-1个方程式的模数的最小公倍数(i从2开始)
    for(int i = 2;i <= n;i++){
        ll mi = mod[i],res = ((yu[i] - ans)%mi + mi)%mi;  //res是等式的右边部分，不能出现负数
        ll gcd = exGcd(M,mi,t,y);        //求出gcd(mi,M)
        if(res % gcd != 0) { cout<<-1<<endl;exit(0); }   //如果等式右边不能整除gcd，方程组无解
        t = qMul(t,res/gcd,mi);            //求出t还要乘上倍数，注意是快速乘取模mi (对谁取模要分清)
        ans += t * M;                               //得到前i个方程的特解（余数）
        M = mi /gcd * M;                         //M等于lcm(M,mi)，注意乘法要在除法后面做，否则会爆long long
        ans = (ans%M+M)%M;                //让特解范围限定在0~(M-1)内，防止会出现负数
    }
    cout<<ans;
    return 0;
}

放一道例题(hard)

U628784 Laz玩游戏
key:ey33