a=p1 ^ a1 * p2 ^ a2 *..........*pn ^ an
b=p1 ^ b1 * p2 ^ b2 *..........*pn ^ bn
gcd(a,b)=p1 ^ min(a1,b1) * p2 ^ min(a2,b2) *..........*pn ^ min(an,bn)
lcm(a,b)=p1 ^ max(a1,b1) * p2 ^ max(a2,b2) *..........*pn ^ max(an,bn)
n = p1 ^ e1* p2 ^ e2 *.....* pn ^en
lcm(a,b) == n , 则 max(a1,b1) ==e1 max(a2,b2) ==e2 ... max(an,bn) == en;
则 当 a 的 因数pi 指数为ei 时， b 的因数 pi 指数 有 [0，ei ] 共 ei 1种选择，
a , b交换也是一样， 对于 两种都选 ei 重复 ，则 对每个指数 ei, 有 2*（ei 1）- 1 种选择
题中要求 i < = j 的对数，除了 （n,n）这一对，另外都重复了 ans = (ans 1)/2
代码语言：javascript复制//LightOJ - 1236 Pairs Forming LCM
//算数基本定理
#include <bits/stdc .h>
#define ll long long
#define LL long long
using namespace std;
const int maxn = 10000010;
bool is_prime[maxn];
int prime[maxn/10];
void get_prime(){
memset(is_prime,0,sizeof(is_prime));
for(int i=2;i<maxn;i ){
if(!is_prime[i])prime[ prime[0]] = i;
for(int j=1;j<=prime[0]&&prime[j]*i<maxn;j ){
is_prime[prime[j]*i] = 1;
if(i%prime[j]==0)break;
}
}
}
ll getfact(ll x){
ll ans = 1,tmp = x;
ll j = 1;
while(j<prime[0]&&prime[j]*prime[j]<=tmp){
if(tmp%prime[j]==0){
ll cnt = 0;
while(tmp%prime[j]==0)tmp/=prime[j],cnt ;
ans*=(1 2*cnt);
}
j ;
}
if(tmp>1)ans*=3;
return (ans 1)/2;
}
int main()
{
get_prime();
int t,cnt=1;
ll a;
scanf("%d",&t);
while(t--){
scanf("%lld",&a);
printf("Case %d: %lldn",cnt ,getfact(a));
}
return 0;
} 
