hdu java大整数gcd_GCD、LCM --算法竞赛专题解析（20）

本系列文章将于2021年整理出版。前驱教材：《算法竞赛入门到进阶》 清华大学出版社

网购：京东 当当   做者签名书：点我

公众号同步：算法专辑

暑假福利：胡说三国

有建议请加QQ 群：567554289html

最大公约数java

1. GCD定义

整数a和b的最大公因数是指能同时整除a和b的最大整数，记为gcd(a, b)。

例如：gcd(15, 81) = 3，gcd(0, 44) = 44，gcd(0, 0) = 0，gcd(-6, -15) = 3，gcd(-17，289) = 17。

注意：因为-a的因子和a的因子相同，所以gcd(a, b) = gcd(|a|, |b|)。编码时只须要关注正整数的最大公因数。c++

2. GCD性质

(1)gcd(a,b) = gcd(a, a+b) = gcd(a, ka+b)

(2)gcd(ka, kb) = k·gcd(a, b)

(3)定义多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)

(4)若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素。这个定理很重要。

(5)gcd(a+cb, b) = gcd(a, b)web

3. GCD编码

编程时能够直接用c++函数std::__gcd(a, b)。注意：参数a和b都应该是正整数，不然可能会返回负数。下面介绍三种算法。算法

3.1 欧几里得算法

用展转相除法求gcd，即gcd(a, b) = gcd(b, a mod b)。代码是：编程

int gcd(int a, int b){ // 通常要求a>=0, b>0。若a=b=0，代码也正确，返回0

return b? gcd(b, a%b):a;

}

这是竞赛中最经常使用的编码，它极为高效，“拉梅定理”给出了复杂度分析。

拉梅定理：用欧几里得算法计算两个正整数的最大公因数，须要的除法次数不会超过两个整数中较小的哪一个十进制数的位数的5倍。

推论：用欧几里得算法求gcd(a, b)，a > b，须要O

(

(

l

o

g

2

a

)

3

)

O((log_2a)^3)O((log2​a)3)次位运算。

欧几里得算法的缺点是须要作除法取模运算，而高精度大数的除法比较耗时，此时能够用“更相减损术”app

不过，在竞赛中不太可能直接使用“更相减损术”和stein算法求最大公约数。下面的介绍，只是为了帮助读者理解GCD的性质。ide

3.2 更相减损术

计算基于这一性质：gcd(a, b) = gcd(b, a-b) = gcd(a, a-b)。svg

计算步骤：用较大的数减较小的数，把所得的差与较小的数比较，而后继续作减法操做，直到减数和差相等为止。

编码也很简单：函数

int gcd(int a, int b){

while(a != b){ //a==b时结束计算

if(a > b) a = a - b;

else b = b - a;

}

return a;

}

更相减损术虽然避免了欧几里得的取模计算，可是计算次数比欧几里得算法多不少，极端状况下须要计算O

(

m

a

x

(

a

,

b

)

)

O(max(a, b))O(max(a,b))次，例如a = 100，b = 1时，需计算100次。

3.3 Stein算法

它是更相减损术的改进。求gcd(a, b)时，能够分为几个状况进行优化：

1)a、b都是偶数。gcd(a, b) = 2gcd(a/2, b/2)，计算减半。

2)a奇b偶(或a偶b奇)。根据这一原理：若k与y互为质数，有gcd(kx, y) = gcd(x, b)。k = 2时，有gcd(a, b) = gcd(a/2, b)，即偶数减半。

3)a、b都是奇数。gcd(a, b ) = gcd( (a+b)/2, (a-b)/2 )。

算法的结束条件仍然是gcd(a, a) = a。

除2操做用移位就能够了，因此Stein算法只用到加减法和移位。

关于高精度大数的GCD计算，读者能够用下面这一题练习，相似的题有hdu 5050。

SuperGCD 洛谷 P2152

题目描述：求2个正整数a，b的最大公约数，0 < a, b ≤ 1

0

10000

10^{10000}1010000。

不过，因为OJ都支持java，比赛的时候直接用java函数处理大数是最简单的：

//洛谷 P2152的java代码

import java.math.*;

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

BigInteger a = in.nextBigInteger();

BigInteger b = in.nextBigInteger();

System.out.println(a.gcd(b));

}

}

4. LCM

a和b的最小公倍数lcm(a, b)，能够从算术基本定理推理获得。

算术基本定理(惟一分解定理)：任何大于1的正整数n均可以惟一分解为有限个素数的乘积：n

=

p

1

c

1

⋅

p

2

c

2

.

.

.

⋅

p

m

c

m

n = p_1^{c_1}·p_2^{c_2}...·p_m^{c_m}n=p1c1​​⋅p2c2​​...⋅pmcm​​，其中c

i

c_ici​都是正整数，p

i

p_ipi​都是素数且从小到大。

设：a

=

p

1

c

1

⋅

p

2

c

2

.

.

.

⋅

p

m

c

m

a = p_1^{c_1}·p_2^{c_2}...·p_m^{c_m}a=p1c1​​⋅p2c2​​...⋅pmcm​​，b

=

p

1

f

1

⋅

p

2

f

2

.

.

.

⋅

p

m

f

m

b = p_1^{f_1}·p_2^{f_2}...·p_m^{f_m}b=p1f1​​⋅p2f2​​...⋅pmfm​​

那么：

g

c

d

(

a

,

b

)

=

p

1

m

i

n

{

c

1

,

f

1

}

⋅

p

2

m

i

n

{

c

2

,

f

2

}

.

.

.

⋅

p

m

m

i

n

{

c

m

,

f

m

}

gcd(a, b) = p_1^{min\{c_1,f_1\}}·p_2^{min\{c2,f2\}}...·p_m^{min\{cm,fm\}}gcd(a,b)=p1min{c1​,f1​}​⋅p2min{c2,f2}​...⋅pmmin{cm,fm}​，

l

c

m

(

a

,

b

)

=

p

1

m

a

x

{

c

1

,

f

1

}

⋅

p

2

m

a

x

{

c

2

,

f

2

}

.

.

.

⋅

p

m

m

a

x

{

c

m

,

f

m

}

lcm(a, b) = p_1^{max\{c_1,f_1\}}·p_2^{max\{c2,f2\}}...·p_m^{max\{cm,fm\}}lcm(a,b)=p1max{c1​,f1​}​⋅p2max{c2,f2}​...⋅pmmax{cm,fm}​

推出：

g

c

d

(

a

,

b

)

∗

l

c

m

(

a

,

b

)

=

a

∗

b

gcd(a, b)*lcm(a,b)=a*bgcd(a,b)∗lcm(a,b)=a∗b，

即:

l

c

m

(

a

,

b

)

=

a

∗

b

/

g

c

d

(

a

,

b

)

=

a

/

g

c

d

(

a

,

b

)

∗

b

lcm(a,b)= a*b/gcd(a, b) = a/gcd(a, b)*blcm(a,b)=a∗b/gcd(a,b)=a/gcd(a,b)∗b。

注意先作除法再作乘法，若是先作乘法可能会溢出

int lcm(int a, int b){

return a / gcd(a, b) * b;

}

5. 例题

(1)hdu 5019

题目描述：给出整数x、y、k，求x、y的第k大公约数。

题解：先求最大公因数d = gcd(x, y)，因为其余公因子都是d的因子，那么从1到d

\sqrt{d}d​(注意不须要到d)逐个检查是否能整除d，便可找到全部公因子。

(2)hdu 2503

题目描述：给出2个分数a/b和c/d，求a/b + c/d，要求是最简形式。

题解：a/b + c/d = (ad + bc) / bd，分子和分母除以二者的最大公约数。

(3)hdu 2504

题目描述：已知a和b，求知足gcd(a,c) = b的最小的c。

题解：暴力搜b到a*b内符合条件的c。

(4)hdu 4497

题目描述：给定两个正整数G、L，问知足gcd(x, y, z) = G和lcm(x, y, z) = L的(x, y, z)有多少个？注意，(1, 2, 3)和(1, 3, 2)是不一样的。

题解。此题利用了GCD的几个性质：

1)若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素；

2)g

c

d

(

a

,

b

)

=

p

1

m

i

n

{

c

1

,

f

1

}

⋅

p

2

m

i

n

{

c

2

,

f

2

}

.

.

.

⋅

p

m

m

i

n

{

c

m

,

f

m

}

gcd(a, b) = p_1^{min\{c_1,f_1\}}·p_2^{min\{c2,f2\}}...·p_m^{min\{cm,fm\}}gcd(a,b)=p1min{c1​,f1​}​⋅p2min{c2,f2}​...⋅pmmin{cm,fm}​

3)l

c

m

(

a

,

b

)

=

p

1

m

a

x

{

c

1

,

f

1

}

⋅

p

2

m

a

x

{

c

2

,

f

2

}

.

.

.

⋅

p

m

m

a

x

{

c

m

,

f

m

}

lcm(a, b) = p_1^{max\{c_1,f_1\}}·p_2^{max\{c2,f2\}}...·p_m^{max\{cm,fm\}}lcm(a,b)=p1max{c1​,f1​}​⋅p2max{c2,f2}​...⋅pmmax{cm,fm}​

若L % G ≠ 0，显然无解。下面分析L % G = 0的状况。

把问题转化为：知足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、y/G、z/G写成：

x/G = p

1

i

1

⋅

p

2

i

2

⋅

p

3

i

3

p_1^{i_1}·p_2^{i_2}·p_3^{i_3}p1i1​​⋅p2i2​​⋅p3i3​​

y/G = p

1

j

1

⋅

p

2

j

2

⋅

p

3

j

3

p_1^{j_1}·p_2^{j_2}·p_3^{j_3}p1j1​​⋅p2j2​​⋅p3j3​​

z/G = p

1

k

1

⋅

p

2

k

2

⋅

p

3

k

3

p_1^{k_1}·p_2^{k_2}·p_3^{k_3}p1k1​​⋅p2k2​​⋅p3k3​​

式子要知足x/G、y/G、z/G互素的条件。以{i

1

,

j

1

,

k

1

i_1, j_1, k_1i1​,j1​,k1​}为例，其中至少有1个应该等于0。

另外，把L/G写成：

L/G = p

1

t

1

⋅

p

2

t

2

⋅

p

3

t

3

p_1^{t_1}·p_2^{t_2}·p_3^{t_3}p1t1​​⋅p2t2​​⋅p3t3​​

式子要知足lcm(x/G，y/G，z/G)= L/G。以{i

1

,

j

1

,

k

1

i_1, j_1, k_1i1​,j1​,k1​}为例，容许的状况是：

1){0, 0, t

1

t_1t1​}，有三种排列；

2){0, t

1

t_1t1​, t

1

t_1t1​}，有三种排列；

3){0, t

1

t_1t1​, 1 ~ t

1

t_1t1​-1}，有(t

1

t_1t1​-1)*6种排列；

加起来一共有 t

1

t_1t1​*6 种排列。

最后问题转化为求t

1

t_1t1​、t

2

t_2t2​、t

3

t_3t3​，即分解 L/G 的质因子。

6. 习题

GCD的题目通常和其余知识点结合出题。

hdu 2104，互素断定

hdu 3092，GCD+彻底背包

hdu 5970，GCD+循环节

hdu 5584，LCM问题

洛谷 P2568 ，GCD + 莫比乌斯反演

洛谷 P2398，GCD求和

洛谷 P1890，询问区间内的GCD

poj 1722，GCD思惟题

poj 2685，GCD+快速幂

poj 3101，大数GCD

poj 2429，GCD + Rabin-Miller测试

最大公约数有多种英文表述：Greatest Common Divisor(GCD)、Greatest Common Denominator、Greatest Common Factor(GCF)、Highest Common Factor (HCF)。 ↩︎

欧几里得《几何本来》是公元前三世纪的著做，中国《九章算术》成于公元一世纪，流行本是三世纪刘徽的注本，都很是古老。“更相减损术”在《九章算术》卷一的“约分”这一节：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”本文给出的代码省去了a、b为偶数的状况，即“可半者半之”。 ↩︎

参考：《算法竞赛入门经典(第2版)》，刘汝佳，清华大学出版社，312页。 ↩︎