本文主要是介绍求两个数所有的公约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述：
-
给定两个正整数a，b（1<=a,b<=100000000）,计算他们公约数的个数。
如给定正整数8和16，他们的公约数有：1、2、4、8，所以输出为4。
- 输入：
-
输入包含多组测试数据，每组测试数据一行，包含两个整数a，b。
- 输出：
-
对于每组测试数据，输出为一个整数，表示a和b的公约数个数。
- 样例输入：
-
8 16 22 16
- 样例输出：
-
4 2
1、简单的从前往后遍历判断是不是公约数，然后计数必定超时；
2、如果要是求最大公约数，我们可以用辗转相除法或迭代法都行，但是题目要求求的是所有的公约数，我们来看一看最大公约数和所有的公约数之间的关系：
所有的公约数必定是最大公约数的因数。证明：假设除了最大公约数GCD外还存在一个公约数N，但是GCD%N!=0，也就是说GCD能被a和b相除，N也能被a和b相除，那么也就是有GCD与N的最小公倍数能被a和b相除，为了保证GCD必须是最大的公约数，则有GCD%N==0
3、问题转化为求最大公约数的所有因数，简单的从1开始到这个最大公约数遍历，判断是否是因数方法也是超时的；
4、我们将这个最大公约数max进行因式分解，如90=2*3*3*5,，我们来看它所有的因数是多少，先列出来，1,2,3,5,6,9,10,15,18,30,45,90，共12个
我们发现有6=2*3,9=3*3,10=2*5等等，即除1外所有的因数都是从2 3 5这3个数中任意挑选出来的，所以对于每个数（2,3,5），对于2可以不选也可以选1个，对于3可以不选可以选1个也可以选2个，对于5可以不选也可以选1个，题目就转化为排列组合问题了，然后将全不选的情况去掉再加上没有考虑的1就是答案了。
#include <stdio.h>
#include <vector>
using namespace std;int gcd(int a,int b){return 0==b?a:gcd(b,a%b);
}
int main(){freopen("C:\\in.txt","r",stdin);int a,b;while(~scanf("%d%d",&a,&b)){int cnt=1;int max=gcd(a,b);int t=0;vector<int> store;for(int i=2;i<=max;i++){if(max%i==0){if(i!=t){t=i;store.push_back(1);}else store.back()++;max/=i;i--;}}for(int i:store){cnt*=(i+1);}printf("%d\n",cnt);}return 0;
}
这篇关于求两个数所有的公约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
