2014年王道论坛研究生机试练习赛（二）set 3 公约数

#include <stdio.h>
#include <map>
#include <iostream>
using namespace std;

int gcd(int x, int y) {
    if(x == 1 || y == 1)
        return 1;

    if(x == y)
        return x;

    if(y > x)
        swap(x,y);

    if((x&1) && (y&1)) {
        return gcd(x-y, y);
    }else if((x&1) &&(!(y&1))) {
        return gcd(x, y/2);
    }else if ((!(x&1)) && (y&1)) {
        return gcd(x/2, y);
    }else{
        return 2*gcd(x/2, y/2);
    }
}

int num(int n) {
    map<int, int> record;
    for(int i = 2; i <= n && n != 1; i ++) {
        while(n >= i && n % i == 0) {
            record[i] ++;
            n /= i;
        }
    }
    int res = 1;
    map<int, int>::iterator it_map;
    for(it_map = record.begin(); it_map != record.end(); it_map ++) {
        res *= (it_map->second+1);
    }
    return res;
}

int main() {
    //freopen("testcase.txt", "r", stdin);
    int a, b;
    while(scanf("%d%d", &a, &b) != EOF) {
        int maxgcd = gcd(a,b);
        
        cout << num(maxgcd) << endl;
    }
    return 0;
}