gcd 与 lcm

几个重要的公式：

\gcd(a,b)=\gcd(a,a+b)=\gcd(b,a\mod b)

\gcd(k\times a,k\times b)=k\times\gcd(a,b)

\gcd(a,b,c)=\gcd(\gcd(a,b),c)

若\gcd(a,b)=d，则\gcd(a/d,b/d)=1，互素

算数基本定理

任何一个大于1的自然数N，如果N不是质数，那么N可以唯一分解成有限个质数的乘积： $n=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$ ，其中 p 为素数。

由此，设

a=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}},b=p_{1}^{f_{1}}p_{2}^{f_{2}}...p_{m}^{f_{m}}

，

则

\gcd(a,b)=p_{1}^{\min(c_{1},f_{1})}p_{2}^{\min(c_{2},f_{2})}...p_{m}^{\min(c_{m},f_{m})}

，

lcm(a,b)=p_{1}^{\max(c_{1},f_{1})}p_{2}^{\max(c_{2},f_{2})}...p_{m}^{\max(c_{m},f_{m})}

。

所以 $lcm(a,b)=a\times b/\gcd(a,b)$ 。

例题

给定

L,G

，问满足

gcd(x,y,z)=G

与

lcm(x,y,z)=L

的

x,y,z

有多少个。

注意问题变形为满足

\gcd(x/G,y/G,z/G)=1,lcm(x/G,y/G,z/G)=L/G

的

(x/G),(y/G),(z/G)

有多少个。

由算术基本定理，令

(x/G) = p_{1}^{i_{1}},p_{2}^{i_{2}},p_{3}^{i_{3}}

(y/G)=p_{1}^{j_{1}},p_{2}^{j_{2}},p_{3}^{j_{3}}

(z/G)=p_{1}^{k_{1}},p_{2}^{k_{2}},p_{3}^{k_{3}}

(L/G)=p_{1}^{t_{1}},p_{2}^{t_{2}},p_{3}^{t_{3}}

。

根据

\gcd

与指数的关系，我们可以知道要使式子成立，则

\min({i_{1},j_{1},k_{1}})=0

满足互素性质，接下来分类讨论取值满足

\max({i_{1},j_{1},k_{1}})=t_{1}

，实际需要分解

G/L

的质因数。

裴蜀定理

若 a,b 为正整数，则有 x,y 使 ax+by=gcd(a,b)

推论：a 与 b 互素当且仅当 ax + by=1，也就是gca(a,b)=1

线性丢番图方程

也叫一元二次不定方程形如

ax+by=c

，

a,b

为常数，

x,y

为变量。

定理：设 d = gcd(a,b)，若d 不能整除 c，方程无解；否则方程有特解 $(x_{0},y_{0})$ ，通解 $x=x_{0}+(b/d)n,y=y_{0}-(a/d)n$ 。

如何求？

扩展欧几里得算法

先用扩展欧几里得求出

ax+by=\gcd(a,b)

的特解

(x_{0},y_{0})

，令此式左右同乘

(c/gcd(a,b))

变为

ax_{0}c/gcd(a,b)+by_{0}c/gcd(a,b)=c

，所以

ax+by=c

的特解就是

x^{'}=x_{0}c\gcd(a,b),y^{'}=y_{0}c\gcd(a,b)

。

CPP

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

同余

一元线性同余方程

逆元

对于非零整数

a,m

，如果存在

b

使得

ab\equiv 1\pmod m

，就称

𝑏

是

a

在模

m

意义下的逆元。
这相当于说，

b

是线性同余方程

ax\equiv 1\pmod m

的解。根据线性同余方程的性质可知，当且仅当

\gcd(a,m)=1

，即

a,m

互素时，逆元

a^{-1}\bmod m

存在，且在模

m

的意义下是唯一的。

求解逆元的多种形式：

单个逆

exgcd

：要求

\gcd(a,m)=1

CPP

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

快速幂：要求

m

为素数
根据费马小定理

a*a^{m-2}=a^{m-1}\equiv 1\pmod m

以及逆元的唯一性可知，逆元

a^{-1}\bmod p

就等于

a^{p-2}\bmod p

，因此可以直接使用快速幂在

O(\log p)

时间内计算：

CPP

int qpow(int a, int b, int m) {
  long long res = 1, po = a;
  for (; b; b >>= 1) {
    if (b & 1) res = res * po % m;
    po = po * po % m;
  }
  return res;
}

int inverse(int a, int p) { return qpow(a, p - 2, p); }

多个逆

线性递推求逆：

同余方程组

𝑥 ≡𝑎1(mod𝑛1)

𝑥 ≡𝑎2(mod𝑛2)

⋮

𝑥 ≡𝑎𝑘(mod𝑛𝑘)

求同余方程组的解

中国剩余定理 CRT

此方法只适用于模数互质的情况，步骤：

计算总模数 $M$ = 各个模数之积
计算 $m_{i}=\frac{M}{n_{i}}$
$exgcd$ 计算 $m_{i}$ 的逆元
方程在模 $M$ 意义下的唯一解： $x=\sum_{i=1}^{n}a_{i}\times m_{i}\times m_{i}^{-1}(mod M)$

CPP

for(int i=1;i<=n;i++){
		read(a[i]); read(b[i]);
		M = M * a[i];//模数的乘积 
	}
	for(int i=1;i<=n;i++){
		__int128 m = M / a[i],x,y;//模数积除以各自的模数 
		exgcd(m,a[i],x,y);//exgcd计算m的逆元 
		ans = (ans + b[i] * m * x % M) % M;//m * m^-1 * 权值 取模总模数 
	}

整除分块

有这样一个问题：

以 n=10 为例

i	1	2	3	4	5	6	7	8	9	10
$\lfloor\frac{n}{i}\rfloor$	10	5	3	2	2	1	1	1	1	1

注意到

\lfloor\frac{n}{i}\rfloor

的值有重复连续的区间，这启示我们按

\lfloor\frac{n}{i}\rfloor

的值分块。

接下来证明分块少于

2\sqrt n

种。
当

i <= \sqrt n

时，

\lfloor\frac{n}{i}\rfloor

的值大于等于

\sqrt n

，共

\sqrt n

个；当

i > \sqrt n

时，

\lfloor\frac{n}{i}\rfloor < \sqrt n

，也有

\sqrt n

个。

当一个区间内的值为

k

时，区间右端点为

\lfloor\frac{x}{k}\rfloor

，证明略。

CPP

ll get(ll x){
	ll res = 0;
	for(ll i=1,j;i<=x;i=j+1){
		j = x / (x / i);
		res += (x/i) * (j - i + 1);
	}
	return res;
}

以 n=10 为例

i	1	2	3	4	5	6	7	8	9	10
$\lfloor\frac{n}{i}\rfloor$	10	5	3	2	2	1	1	1	1	1
$i\times \lfloor \frac{n}{i} \rfloor$	10	10	9	12	10	6	7	8	9	10

相当于每个区间是一个首项为

\lfloor\frac{x}{i}\rfloor\times i

，尾项为

\lfloor\frac{x}{i}\rfloor\times\lfloor\frac{x}{k}\rfloor

，长度为

(r - l + 1)

，公差为

\lfloor\frac{n}{i}\rfloor

的等差数列。

CPP

ll get(ll x){
	ll res = 0;
	for(ll i=1,j;i<=x;i=j+1){
		ll k = x / i;
		j = x / k;
		res += k * (i + j) * (j - i + 1) / 2; 
	}
	return res;
}

例题

模拟赛遇到了，没做出来。给定

a,b

两个序列，定义

c_{i} = \sum_{j=1}^{i} a_{\lfloor\frac{i}{j}\rfloor} \times b_{i\mod j}

，求序列

c

。

和上面的结论一样，根据整除分块，

\lfloor\frac{n}{i}\rfloor

相同的

a

是连续的一段，且只有

sqrt_{n}

级别，注意到

i \mod j

在这相同的一段中是公差为

\lfloor\frac{n}{i}\rfloor

的等差数列的形式，所以说我们就可以利用根号分治的思想，小于根号 k 的暴力计算，大于根号 k 的进行下标的等差数列前缀和预处理，利用整除分块快速计算。

-2025.11.18

数学知识

文章操作

gcd 与 lcm

算数基本定理

任何一个大于1的自然数N，如果N不是质数，那么N可以唯一分解成有限个质数的乘积： $n=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$ ，其中 p 为素数。

所以 $lcm(a,b)=a\times b/\gcd(a,b)$ 。

例题

裴蜀定理

若 a,b 为正整数，则有 x,y 使 ax+by=gcd(a,b)

推论：a 与 b 互素当且仅当 ax + by=1，也就是gca(a,b)=1

线性丢番图方程

定理：设 d = gcd(a,b)，若d 不能整除 c，方程无解；否则方程有特解 $(x_{0},y_{0})$ ，通解 $x=x_{0}+(b/d)n,y=y_{0}-(a/d)n$ 。

扩展欧几里得算法

同余

一元线性同余方程

逆元

单个逆

多个逆

同余方程组

中国剩余定理 CRT

整除分块

相关推荐

评论

数学知识

文章操作

gcd 与 lcm

算数基本定理

任何一个大于1的自然数N，如果N不是质数，那么N可以唯一分解成有限个质数的乘积：n=p1c1p2c2...pmcmn=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}n=p1c1​​p2c2​​...pmcm​​，其中 p 为素数。

所以 lcm(a,b)=a×b/gcd⁡(a,b)lcm(a,b)=a\times b/\gcd(a,b)lcm(a,b)=a×b/gcd(a,b)。

例题

裴蜀定理

若 a,b 为正整数，则有 x,y 使 ax+by=gcd(a,b)

推论：a 与 b 互素当且仅当 ax + by=1，也就是gca(a,b)=1

线性丢番图方程

定理：设 d = gcd(a,b)，若d 不能整除 c，方程无解；否则方程有特解 (x0,y0)(x_{0},y_{0})(x0​,y0​)，通解 x=x0+(b/d)n,y=y0−(a/d)nx=x_{0}+(b/d)n,y=y_{0}-(a/d)nx=x0​+(b/d)n,y=y0​−(a/d)n。

扩展欧几里得算法

同余

一元线性同余方程

逆元

单个逆

多个逆

同余方程组

中国剩余定理 CRT

整除分块

相关推荐

评论

任何一个大于1的自然数N，如果N不是质数，那么N可以唯一分解成有限个质数的乘积： $n=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$ ，其中 p 为素数。

所以 $lcm(a,b)=a\times b/\gcd(a,b)$ 。

定理：设 d = gcd(a,b)，若d 不能整除 c，方程无解；否则方程有特解 $(x_{0},y_{0})$ ，通解 $x=x_{0}+(b/d)n,y=y_{0}-(a/d)n$ 。