2つの数のすべての公約数を求めます

タイトルの説明:
2つの正の整数a,b(1<=a,b<=1億円)を与え、それらの公約数の個数を計算する.正の整数8,16が与えられた場合、彼らの公約数は1,2,4,8であるため、出力は4である.
入力:
入力には、複数のテストデータが含まれ、各テストデータの1行に2つの整数a,bが含まれます.
出力:
各テストデータのセットについて、出力は整数であり、aとbの公約数を表す.
サンプル入力:

8 16
22 16

サンプル出力:

4
2

分析:
1、简単に前から后まで遍歴して公约数かどうかを判断して、それからカウントは必ずタイムアウトします;
2、もし最大公約数を求めるならば、私达は転がり相除法あるいは反復法を使ってもいいですが、テーマはすべての公約数を求めることを要求して、私达は最大公約数とすべての公約数の间の関系を见てみましょう:
すべての公約数は必ず最大公約数の因数である.証明:最大公約数GCDに加えて1つの公約数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
",cnt);
    }

    return 0;
}