一.概述
最大公约数（GCD）和最小公倍数（Least Common Multiple，LCM）
在C++中，可以使用 std::__gcd(a, b)来计算最大公约数
1.欧几里德算法/辗转相除法
int gcd(int a,int b){return b?gcd(b, a%b):a;
}2.lcm
int lcm(int a,int b){return a/gcd(a, b)*b;
}3.gcd的性质
- gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b)
- gcd(ka, kb) = k·gcd(a, b)
- 多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)。
- 若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素。这个定理很重要。
- gcd(a+cb, b) = gcd(a, b)
- 裴蜀定理：如果两个整数的最大公约数是d， 那么方程ax+by=d一定有解。
二.实战演练
1.等差数列
题目描述：
分析：
把n个数据排序，计算它们的间隔，对所有间隔做GCD，结果为公差。最少数量等于：（最大值-最小值）/公差+1。
代码实现：
//等差数列
#include<iostream>
#include<algorithm>using namespace std;const int N=1e5;long long n,a[N],gcdd=0;long long gcd(long long a,long long b){return b?gcd(b, a%b):a;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(long long i=0;i<n;i++){cin>>a[i];}sort(a, a+n);//0和任意一个数x的最大公约数是xfor(long long i=1;i<n;i++){gcdd=gcd(gcdd, a[i]-a[i-1]);}if(gcdd==0){cout<<n<<'\n';}elsecout<<(a[n-1]-a[0])/gcdd+1<<'\n';return 0;
}2.Hankson的趣味题
题目描述：
分析：
其实就是暴力，但是因为需要枚举的区间太大了，所以需要剪枝优化。
从1开始枚举到b1，但是这样枚举的空间就太大了，所以需要优化。
如果这个数能够被b1整除，那么才需要去接着进行判断。
另外一个就是通过分解因子，x*y=b1。
代码实现：
//Hankson的趣味题
#include<bits/stdc++.h>using namespace std;long long gcd(long long a,long long b){return b?gcd(b, a%b):a;
}long long lcm(long long a,long long b){return a/gcd(a, b)*b;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;while(n--){long long a1,a0,b1,b0;cin>>a0>>a1>>b0>>b1;int ans=0;for(long long i=1;i<=sqrt((double)b1);i++){if(b1%i==0){if(gcd(i,a0)==a1&&lcm(i,b0)==b1){ans++;}long long y=b1/i;if(y==i){continue;}else{if(gcd(y, a0)==a1&&lcm(y,b0)==b1){ans++;}}}}cout<<ans<<'\n';}return 0;
}3.最大比例
题目描述：
问题分析：
对于该题，将输入进来的数据先排序。
我们可能会想，能不能用xn/xn-1来获得这个比值呢？也就是说依次的去做除法，然后找到这些倍数的最大公约数。
这个题最烦人的点在于，输出是一个分数，那我们就不得不分别的去处理分子与分母了。
可以分别去找分子和分母的最大公约数。
这个比值的获取，可以通过xn/xn-1，也可以通过xn/x0.
代码实现：
//最大比例
#include<iostream>
#include<algorithm>using namespace std;const int N=105;long long x[N],a[N],b[N];
int n;
//此函数是用来求 a^{n1} a^{n2} 中的a的
long long gcd_sub(long long a,long long b){if(a<b){swap(a, b);}if(b==1)return a;return gcd_sub(b, a/b);
}long long gcd(long long a,long long b){return b?gcd(b, a%b):a;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);long long cnt=0;cin>>n;for(int i=0;i<n;i++){cin>>x[i];}//排序sort(x,x+n);for(int i=1;i<n;i++){//获取分子和分母long long d=gcd(x[i], x[0]);a[cnt]=x[i]/d;b[cnt]=x[0]/d;cnt++;}long long up=a[0],down=b[0];for(int i=1;i<cnt;i++){up=gcd_sub(a[i], up);down=gcd_sub(b[i], down);}cout<<up<<'/'<<down<<'\n';return 0;
}
