全文目录
零、写在前面
一、主要知识点
最小公倍数
二、课后习题
1819. 序列中不同最大公约数的数目
写在最后
零、写在前面
这个系列不经常更新，今天我尝试使用markdown来编辑这些内容完善这部分的所有题解吧。
【第24题】给定 a 和 b，求它们的最小公倍数 | 最小公倍数 和 最大公约数有什么关系呢？
一、主要知识点
最大公倍数和最小公倍数的关系
最小公倍数
求最小公倍数的方法
int gcd(int a, int b) { //辗转相除法求最大公约数 if(!b) { return a; } return gcd(b, a % b); } int main() { int a, b; while(scanf("%d %d", &a, &b) != EOF) { printf("%d\n", a / gcd(a, b) * b); // 两者乘积除最大公约数可以得到最小公倍数 } return 0; }
二、课后习题
1819. 序列中不同最大公约数的数目
题目链接
给你一个由正整数组成的数组 nums 。
数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
解题思路
首先，每个元素必然是一个一个子序列中的公约数
然后从1到最大来判断是否是某个子序列的公约数
其中判断i是否是某个子序列的公约数的时候就是 判断i 、2i、3i…max的公约数是否是i 因为这个序列的公约数必有i 元素越来越多的时候公约数应该越来越小，保证公约数最小的时候是i就是 如果不是就不是
int gcd(int a, int b){ return !b ? a : gcd( b , a % b); } int countDifferentSubsequenceGCDs(int* nums, int numsSize){ bool f[200001] = {0}; int max = 0 , ans = 0; for(int i = 0;i < numsSize;++i){ if(nums[i] > max) max = nums[i];//确定最大值 if(!f[nums[i]]){ ans ++; //将每个元素加进去 f[nums[i]]++; } } for(int i = 1;i <= max;++i){ if(f[i]) continue; //已加入元素 int g = 0,j; //0和任何数求最大公约数会得到那个数字 不信你跑跑-.- for(j = i; j <= max;j += i){ if(f[j]){ g = gcd(j,g); //求最大的公约数 if(g == i) break; } } if(g == i) ans++; } return ans; }
结束
