GCD作为缩写意义有多种。它通常表示多核编程的解决方法,也有最大公约数(greatest common divisor,简写为gcd;或highest common factor,简写为hcf),此外它还是共产党的拼音缩写和游戏《鬼吹灯外传》的拼音缩写和“创意群总监”的英文缩写。在这里我讲一下GCD作为最大公约数(greatest common divisor,简写为gcd;或highest common factor,简写为hcf)时的一些计算方法。
GCD
Common GCD(I)
题目:给定两个数 $ A,B $ ,求他们的最大公约数
Example 1 :
输入:4 9
输出:1
Example 2 :
输入:3 9
输出:3
P.S. $ A,B \leq 1e^{6} $
这种题目范围比较小也比较简单可以直接暴力求出
1 | /* |
Common GCD(II)
题目:输入N个数, $a_1,a_2,a_3, …… , a_n$ 求这N个数的最大公约数
Example 1 :
输入:
5
2 4 6 8 10
输出:
2
Example 2 :
输入:
2
7 49
输出:
7
P.S. P.S. $ a_i \leq 10^9 ,N \leq 10^8 $ 题目保证数据全随机化
这种题目数据范围比较大也题目难度比较简单可以直接暴力求出,并且注意到“数据全随机化”,这意味着在数据大而且多的情况下往往得到gcd=1,这样的话在gcd=1的时候直接退出程序可以节约一点时间
1 | /* |