求两个数所有的公约数 - c++编程基础

题目描述：

给定两个正整数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 
            
             
#include 
             
               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
              
                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; }