求两个数所有的公约数

题目描述：

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

求两个数所有的公约数,布布扣,bubuko.com

求两个数所有的公约数

原文：http://blog.csdn.net/starcuan/article/details/20315219