hdu 4497 GCD and LCM（2013 ACM-ICPC吉林通化全國邀請賽——題目重現）

    質分解 + 簡單計數。當時去比賽的時候太年輕了。。。這道題都沒敢想。現在回過頭來做了一下，發現挺簡單的，當時沒做這道題真是挺遺憾的。這道題就是把lcm  / gcd 質分解，統計每個質因子的個數，然後就可以統計出總數了。           統計的時候假如有2個3，這樣的話肯定是有一個元素是含有全部的2個3的，也肯定有一個元素沒有3，於是我們就可以直接得出，統計個數為元素個數x6， 然後每個質因子分配情況互不影響，於是可以用乘法原理。就可以得出最終答案了。    

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<vector>  
#include<cmath>  
  
#define LL long long  
#define CLR(a, b) memset(a, b, sizeof(a))  
#define SL(a) strlen(a)  
  
using namespace std;  
  
const int N = 111111;  
  
vector<int> hav;  
bool isp[N];  
int p[N], cnt;  
  
void getp()  
{  
    int i, j;cnt = 0;  
    isp[0] = isp[1] = 1;  
    for(i = 2; i < N; i ++)  
    {  
        if(!isp[i])  
        {  
            p[cnt ++] = i;  
            if(i <= 1111)for(j = i * i; j < N; j += i) isp[j] = 1;  
        }  
    }  
}  
  
void get_hav(int h)  
{  
    int i;  
    for(i = 0; i < cnt && h > 1; i ++)  
    {  
        if(h % p[i] == 0)  
        {  
            h /= p[i];  
            hav.push_back(p[i]);  
            i --;  
        }  
    }  
    if(!hav.size() && h != 1) hav.push_back(h);  
}  
  
int main()  
{  
    int l, g, i, num, t;  
    LL ans;  
    getp();  
    cin >> t;  
    while(t --)  
    {  
        cin >> g >> l;  
        if(l % g != 0) puts("0");  
        else  
        {  
            l /= g;  
            ans = 1;  
            hav.clear();  
            get_hav(l);  
            hav.push_back(-1);  
            num = 0;  
            for(i = 0; i < hav.size() - 1; i ++)  
            {  
                if(hav[i] == hav[i + 1])  
                {  
                    num ++;  
                }  
                else  
                {  
                    num ++;  
                    ans *= (6 * num);  
                    num = 0;  
                }  
            }  
            cout << ans << endl;  
        }  
    }  
}