福建建设人才网站,做有后台的网站,成都蜀美网站建设,湖南seo推广方法报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周。 在QQ群上交流答疑如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周。 在QQ群上交流答疑 文章目录 1. GCD1.1 GCD概念1.2 GCD性质1.2 GCD编码实现 2. LCM3. 例题3.1 等差数列3.2 Hankson的趣味题 3.3 最大比例 第16周: GCD和LCM 最大公约数GCD和最小公倍数Least Common MultipleLCM研究整除的性质非常古老2000多年前就得到了很好的研究。由于简单易懂有较广泛的应用是竞赛中频繁出现的考点。 最大公约数有多种英文表述Greatest Common Divisor(GCD)、Greatest Common Denominator、Greatest Common Factor(GCF)、Highest Common Factor (HCF)。
1. GCD
1.1 GCD概念 整数a和b的最大公约数是能同时整除a和b的最大整数记为gcd(a, b)。 负整数也可以算gcd不过由于-a的因子和a的因子相同编码时只需要关注正整数的最大公约数。下面用c函数std::__gcd(a, b)演示gcd的计算结果。
#includebits/stdc.h
using namespace std;
int main(){cout __gcd(45,9) \n; // 9cout __gcd(0,42) \n; // 42cout __gcd(42,0) \n; // 42cout __gcd(0,0) \n; // 0cout __gcd(20,15) \n; // 5cout __gcd(-20,15) \n; // -5cout __gcd(20,-15) \n; // 5cout __gcd(-20,-15)\n; // -5cout __gcd((long long)98938441343232,(long long)33422)\n; //2
}Java没有自带GCD库函数。 Python自带的GCD函数只返回正整数。
from math import *
print(gcd(45, 9)) # 9
print(gcd(0, 42)) # 42
print(gcd(42, 0)) # 42
print(gcd(0, 0)) # 0
print(gcd(20, 15)) # 5
print(gcd(-20, 15)) # 5
print(gcd(20, -15)) # 5
print(gcd(-20, -15)) # 5
print(gcd(98938441343232, 33422)) # 21.2 GCD性质 GCD有关的题目一般会考核GCD的性质。 1gcd(a, b) gcd(a, ab) gcd(a, k·ab) 2gcd(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互素。这个定理很重要。 5gcd(acb, b) gcd(a, b)
1.2 GCD编码实现 编程时可以不用自己写GCD代码而是直接使用c函数std::__gcd(a, b)。如果自己编码也很简单用欧几里得算法又称为辗转相除法即gcd(a, b) gcd(b, a mod b)。
int gcd(int a, int b){ // 一般要求a0, b0。若ab0代码也正确返回0return b? gcd(b, a%b):a;
}Java的gcd需要自己写。
import java.math.BigInteger;
public class Main {public static void main(String[] args) {System.out.println(gcd(45, 9)); // 9System.out.println(gcd(0, 42)); // 42System.out.println(gcd(42, 0)); // 42System.out.println(gcd(0, 0)); // 0System.out.println(gcd(20, 15)); // 5System.out.println(gcd(-20, 15)); // -5System.out.println(gcd(20, -15)); // 5System.out.println(gcd(-20, -15)); // -5System.out.println(gcd(new BigInteger(98938441343232), new BigInteger(33422))); // 2}public static long gcd(long a, long b) {if (b 0) return a; return gcd(b, a % b);}public static BigInteger gcd(BigInteger a, BigInteger b) {return a.gcd(b);}
}python。自己写gcd()函数可能返回负数。
def gcd(a,b):if b 0:return aelse: return gcd(b,a%b)
print(gcd(45, 9)) # 9
print(gcd(0, 42)) # 42
print(gcd(42, 0)) # 42
print(gcd(0, 0)) # 0
print(gcd(20, 15)) # 5
print(gcd(-20, 15)) # 5
print(gcd(20, -15)) # -5
print(gcd(-20, -15)) # -5
print(gcd(98938441343232, 33422)) # 22. LCM 最小公倍数LCMthe Least Common Multiple。a和b的最小公倍数lcm(a, b)从算术基本定理推理得到。 算术基本定理任何大于1的正整数n都可以唯一分解为有限个素数的乘积 n p 1 c 1 p 2 c 2 . . . p m c m n p_1^{c1}p_2^{c2}...p_m^{cm} np1c1p2c2...pmcm其中ci都是正整数 p i p_i pi都是素数且从小到大。 设 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 a p_1^{c1}p_2^{c2}...p_m^{cm}b p_1^{f1}p_2^{f2}...p_m^{fm} ap1c1p2c2...pmcmbp1f1p2f2...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\{c1,f1\}}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\{c1,f1\}}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*b gcd(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)*b lcm(a,b)a∗b/gcd(a,b)a/gcd(a,b)∗b
c代码
int lcm(int a, int b){ //需要的时候把int改成long longreturn a / gcd(a, b) * b; //先做除法再做乘法防止先做乘法溢出
}java代码 public static int gcd(int a, int b) {if (b 0) return a; return gcd(b, a % b);}public static long lcm(int a, int b) {return (long) a / gcd(a, b) * b;}python代码 在Python新版本中有库函数lcm()它可以带多个参数。
from math import *
print(lcm(3,6,8,9)) #输出72也可以自己写一个
from math import *
def lcm(x,y): return x//gcd(x,y)*y3. 例题 GCD和LCM的题目太多了随便到哪个OJ都能以GCD为算法关键词搜出很多。
3.1 等差数列 等差数列 【题目描述】数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列只记得其中N个整数。现在给出这N个整数小明想知道包含这N个整数的最短的等差数列有几项? 【输入描述】输入的第一行包含一个整数N。 第二行包含N个整数A1,A2,···,AN。(注意A1 ∼AN并不一定是按等差数列中的顺序给出) (对于所有评测用例2≤N≤1000000≤Ai≤ 1 0 9 10^9 109。) 【输出描述】输出一个整数表示答案 所有数字间距离最小的间隔是公差吗 并不是例如{257}最小的间隔是2但公差不是2是1。 这是gcd问题。把n个数据排序计算它们的间隔对所有间隔做GCD结果为公差。最少数量等于最大值-最小值/公差1。 c代码
#includebits/stdc.h
using namespace std;
int a[100000];
int main(){int n; cinn;for(int i0;in;i) cina[i];sort(a,an);int d0;for(int i1;in;i) d __gcd(d,a[i]-a[i-1]); if(d0) coutnendl;else printf(%d\n,(a[n - 1] - a[0]) / d 1);return 0;
}Java代码
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[] a new int[n];for (int i 0; i n; i) a[i] sc.nextInt(); Arrays.sort(a);int d 0;for (int i 1; i n; i) d gcd(d, a[i] - a[i - 1]); if (d 0) System.out.println(n);else System.out.println((a[n - 1] - a[0]) / d 1); }public static int gcd(int a, int b) {if (b 0) return a; return gcd(b, a % b);}
}python代码
from math import *
nint(input())
alist(map(int,input().split()))
a.sort()
d0
for i in range(1,n): dgcd(d,a[i]-a[i-1])
if d0: print(n)
else: print((a[-1]-a[0])//d1)3.2 Hankson的趣味题 Hankson的趣味题 【题目描述】刚刚放学回家的Hankson正在思考一个有趣的问题。今天在课堂上老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”这个问题是这样的已知正整数a0,a1,b0,b1设某未知正整数x满足:
x和a0 的最大公约数是a1x和b0的最小公倍数是b1。 Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后他发现这样的x并不唯一甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。 【输入格式】输入第一行为一个正整数n表示有n组输入数据。 接下来的n行每行一组输入数据为四个正整数a0a1b0b1每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除b1能被b0整除。 数据规模对于100%的数据保证有1≤a0a1b0b1≤2,000,000,000且n≤2000。 【输出格式】输出共n行。每组输入数据的输出结果占一行为一个整数。对于每组数据若不存在这样的x请输出0若存在这样的x请输出满足条件的x的个数。 最简单的暴力法是把所有可能的x试一遍。x的范围是x ≤ b1。 但是由于本题的数据范围是 b 1 ≤ 2 × 1 0 9 b1 ≤ 2×10^9 b1≤2×109肯定超时。 若x是b1的因子那么x*y b1y也可能是答案。所以只需要在范围xsqrt(b1)内查询同时判断y就行了。 但是这样还是超时因为gcd计算也要花时间最后加上一个优化if(b1%x0)表示b1是x的公倍数。
c代码
#includebits/stdc.h
using namespace std;
int lcm(int a, int b){ return a / __gcd(a, b) * b;}
int main() {int n; scanf(%d,n);while(n--) {int a0,a1,b0,b1;cin a0a1b0b1;int ans0;for(int x1;x sqrt(b1);x){if(b1%x 0){ //优化if(__gcd(x,a0)a1 lcm(x,b0)b1) ans;int y b1/x; //另外一个因子if(xy) continue;if(__gcd(y,a0)a1 lcm(y,b0)b1) ans;}}cout ans endl;}return 0;
}java
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();while (n-- 0) {int a0 sc.nextInt();int a1 sc.nextInt();int b0 sc.nextInt();int b1 sc.nextInt();int ans 0;for (int x 1; x Math.sqrt(b1); x) {if (b1 % x 0) {if (gcd(x, a0) a1 lcm(x, b0) b1) ans; int y b1 / x;if (x y) continue; if (gcd(y, a0) a1 lcm(y, b0) b1) ans; }}System.out.println(ans);}}public static int gcd(int a, int b) {if (b 0) return a; return gcd(b, a % b);}public static int lcm(int a, int b) {return a / gcd(a, b) * b;}
}python
from math import *
def lcm(x,y): return x//gcd(x,y)*y
nint(input())
for _ in range(n):a0,a1,b0,b1 map(int,input().split())ans0for x in range(1,int(sqrt(b1))1):if b1 % x 0:if gcd(x,a0)a1 and lcm(x,b0)b1: ans1y b1//xif xy: continueif gcd(y,a0)a1 and lcm(y,b0)b1: ans1print(ans)3.3 最大比例 最大比例 【题目描述】X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。并且相邻的两个级别间的比例是个固定值。也就是说所有级别的奖金数构成了一个等比数列。比如16,24,36,54 其等比值为3/2 现在我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。 【输入格式】第一行为数字 N (0N100)表示接下的一行包含N个正整数。第二行N个正整数Xi(Xi1 000 000 000 000)用空格分开。每个整数表示调查到的某人的奖金数额。 【输出格式】一个形如A/B的分数要求A、B互质。表示可能的最大比例系数。 测试数据保证了输入格式正确并且最大比例是存在的。 先试试暴力法。 把这些数字排个序然后算出相邻两个数的比值。最小的那个比值K是否就是答案呢 不是。例如{2, 16, 64}比值是16/2864/164最小比值K4。但是原序列是{2, 4, 8, 16, 32, 64}比值是2。 所以答案肯定比K小如何求出答案如果一个个试比K小的分数肯定会超时。 再用另一个思路这次不是算相邻两个数的比值而是每个数对第一个数的比值会不会好些 设原序列是 x , x q 1 , x q 2 , . . . , x q n − 1 {x, xq^1, xq^2, ..., xq^{n-1}} x,xq1,xq2,...,xqn−1从中挑出一些数字 x q c , x q d , . . . , x q y , x q z {xq^c, xq^d, ..., xq^y, xq^z} xqc,xqd,...,xqy,xqz它们之间的两两相除得到一个比值序列 1 , q d − c , . . . , q z − y {1, q^{d-c}, ... , q^{z-y}} 1,qd−c,...,qz−y这其中的一些数字可能是相同的有点麻烦。 或者算它们对第一个数的比值得 1 , q d − c , . . . , q y − c , q z − c 1 , q k d , . . . , q k y , q k z {1, q^{d-c}, ... , q^{y-c} , q^{z-c}} {1, q^{kd}, ... , q^{ky} , q^{kz}} 1,qd−c,...,qy−c,qz−c1,qkd,...,qky,qkz 这个序列内的所有数字肯定不同。令 q a / b q a/b qa/b那么这个序列变成了 1 , ( a / b ) k d , . . . , ( a / b ) k y , ( a / b ) k z {1, (a/b)^{kd}, ..., (a/b)^{ky}, (a/b)^{kz}} 1,(a/b)kd,...,(a/b)ky,(a/b)kz。分成分子和分母两个序列分别是 A a k d , . . . , a k y , a k z , B b k d , . . . , b k y , b k z A{a^{kd}, ..., a^{ky}, a^{kz}}, B{b^{kd}, ..., b^{ky}, b^{kz}} Aakd,...,aky,akz,Bbkd,...,bky,bkz。 已知这两个序列A、B中每个元素的值求a和b。 例如A{16, 128, 512, 1024}得a2即 A 2 4 , 2 7 , 2 9 , 2 10 A{2^4, 2^7, 2^9, 2^{10}} A24,27,29,210。如何根据A求a 显然A中每个数除以前面一个数都能够整除得到a的一个倍数但是这个倍数还不是a需要继续除直到得到a为止。以前2个数 2 4 , 2 7 {2^4, 2^7} 24,27为例计算步骤是 2 7 / 2 4 2 3 2 4 / 2 3 2 1 2 3 / 2 1 2 2 2 2 / 2 1 2 2 1 / 2 1 1 2^7/2^42^32^4/2^32^12^3/2^12^22^2/2^122^1/2^11 27/242324/232123/212222/21221/211结束得a2。这是一个辗转相除的过程。 对A中所有元素都执行这个过程就得到了a。下面代码中的gcd_sub()完成了这一任务。
c代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 105;
ll x[N],a[N],b[N];
ll gcd_sub(ll a,ll b){if(ab) swap(a,b);if(b1) return a;return gcd_sub(b,a/b);
}
int main(){int n; cin n;ll cnt0;for(int i0;in;i) cinx[i];sort(x,xn); //排序for(int i1;in;i){ll d __gcd(x[i],x[0]);a[cnt] x[i]/d;b[cnt] x[0]/d; //约分,得分子a / 分母bcnt;}ll up a[0], down b[0];for(int i1;icnt;i){up gcd_sub(up,a[i]); //求分子down gcd_sub(down,b[i]); //求分母}coutup/downendl;return 0;
}java
import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();long[] x new long[n];for (int i 0; i n; i) x[i] sc.nextLong(); Arrays.sort(x);long[] a new long[n - 1];long[] b new long[n - 1];int cnt 0;for (int i 1; i n; i) {long d gcd(x[i], x[0]);a[cnt] x[i] / d;b[cnt] x[0] / d;cnt;}long up a[0];long down b[0];for (int i 1; i cnt; i) {up gcdSub(up, a[i]);down gcdSub(down, b[i]);}System.out.println(up / down);}public static long gcd(long a, long b) {if (b 0) return a; return gcd(b, a % b);}public static long gcdSub(long a, long b) {if (a b) {long temp a; a b; b temp; }if(b1) return a;return gcdSub(b,a/b);}
}python
from math import *
def gcd_sub(a,b):if ab: a,b b,aif b1: return areturn gcd_sub(b,a//b);
n int(input())
x list(set(map(int,input().split()))) #set有去重的作用
x.sort()
n len(x)
a[]
b[]
for i in range(1,n):d gcd(x[i],x[0])a.append(x[i]//d)b.append(x[0]//d)
n len(a)
up a[0]
down b[0]
for i in range(1,n):up gcd_sub(up,a[i])down gcd_sub(down,b[i])
print(%d/%d%(up,down))其他练习请到这里洛谷的GCD题目
