备战蓝桥--GCD和LCM(进阶)
特殊注意事项
gcd:最大公约数 lcm:最小公倍数 其他定义就省略了,自己查查吧
gcd最大公约数
基本案例
gcd( 15 , 81 ) =3 gcd ( 0 , 44 ) = 44 gcd( 0 , 0 ) =0 gcd ( -6 , -15 ) = 3 两个负数的最大公约数为正数 gcd( -17 , 289 ) = 17 一正一负也得正数
性质
(1)gcd(a,b) = gcd(a,a+b) =gcd(a,ka+b) =gcd(kb+a,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,即剩下两个数互质
代码实现
(1)最简单的就是用库函数, c++:std::__gcd(a,b) (2)辗转相除法
int gcd(int a,int b) { return b?gcd(b,a%b):a; }
LCM最小公倍数
求出gcd后就超级简单了 lcm(a,b) =a*b/gcd(a,b);
int lcm(int a,int b) { return a/gcd(a,b)*b; }
**小技巧:**先乘再除,防止数据溢出
简单基本应用
案例一、蓝桥–等差数列:http://oj.ecustacm.cn/problem.php?id=1466 案例二、蓝桥–核桃的数量:http://oj.ecustacm.cn/problem.php?id=1435 案例三、最大最小公倍数:蓝桥杯VIP试题(找不到资源,呜呜呜)
案例一: 自己想法:利用等差数列的性质,枚举公差,排序后一步步往后比对 gcdAC代码:
#include <bits/stdc++.h> using namespace std; #define MAXSIZE 1000000 int num[MAXSIZE]; int main() { int n;cin>>n; for(int i=0;i<n;i++) { cin>>num[i]; } sort(num,num+n); int pre=1; for(int i=1;i<n;i++) { int t=num[i]-num[i-1]; //相邻两个数的差值 if(i==1) pre=t; pre=__gcd(pre,t); } //cout<<pre<<endl; if(pre==0) cout<<n; //注意数列全部相等,即公差为0的情况 else cout<<(num[n-1]-num[0])/pre+1; return 0; }
案例二AC代码:
#include <bits/stdc++.h> using namespace std; int main() { int a,b,c; cin>>a>>b>>c; int g=__gcd(a,b); g=a*b/g; int t=__gcd(g,c); cout<<(g*c)/t; return 0; }
案例三、最大最小公倍数 题意 给一个数n,在1–n中任选3个数,求出这个三个数的最小公倍数。然后求出这个最小公倍数的最大值。
分析 当n比较小时(在要求的时间范围内时)可以直接用暴力法从n、n-1、n-2贪心找 当n比较大时,暴力法就不行了 用分析法: 这三个数应该两两互质,如果不互质就会有公约数,最小公倍数就会变小 相邻的两个数必然互质 利用贪心算法,从最大的数开始考虑 (1)当n为奇数时,n-1为偶数,n-2为奇数,n-1和n-2必然互质(很接近的两个奇数肯定互质),此时n、n-1、n-2互质,最小公倍数为三者乘积结果最大 (2)当n为偶数时,n-1为奇数,n-2为偶数(此时n和n-2有公因子2,丢掉考虑n-3),n-3为奇数,n-1和n-3肯定互质(相邻奇数),只需考虑n和n-3 n和n-3要么都是3的倍数,要么就互质 若n不能被3整除,则n-3也不能被3整除,二者互质,n、n-1、n-3为三个数 若n能被3整除,则n-3也能,丢掉n,考虑n-1 、n-2、n-3,n-1和n-3都是奇数,则三者满足条件 从分析可以看出,满足条件三个质数必然包含在最大的4个数里面
代码:
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int ans=1; if(n%2) //n为奇数 { ans=n*(n-1)*(n-2); } else { if(n%3) ans=(n-1)*(n-2)*(n-3); else ans=n*(n-1)*(n-3); } return 0; }
难题提高应用
最大比例:https://www.lanqiao.cn/problems/120/learning/ 或者 http://oj.ecustacm.cn/problem.php?id=1289 Hankson的趣味题:https://www.lanqiao.cn/problems/520/learning/ 最大体积(VIP试题):http://lx.lanqiao.cn/problem.page?gpid=T261