题意 ：给你一个数n 求满足lcm(a, b) == n， a <= b 的 (a,b) 的个数
唯一分解定理内容：对于任意一个大于1的数都可以唯一分解为若干个素数的乘积，即n=a1^b1*a2^b2*......an^bn;
容易知道 n 是由a和b的所有素因子构成的，n的中的素因子指数等于a,b中相同素因子指数较大的指数。
先将n分解为素数指数积的形式 n = π(pi^ei) 那么对于每个素因子pi pi在a,b中的指数ai, bi 至少有一个等于pi， 另一个小于等于pi
先不考虑a, b的大小 对于每个素因子pi
1. 在a中的指数 ai == ei 那么 pi 在 b 中的指数可取 [0, ei] 中的所有数 有 ei + 1 种情况
2. 在a中的指数 ai < ei 即 ai 在 [0, ei) 中 那么 pi 在 b 中的指数只能取 ei 有 ei 种情况
那么对与每个素因子都有 2*ei + 1种情况 也就是满足条件的 (a, b) 有 π(2*ei + 1)个 考虑大小时 除了 (n, n) 所有的情况都出现了两次 那么满足a<=b的有 (π(2*ei + 1)) / 2 + 1 个
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7+5;
int prim[N/10], m;
bool vis[N];
void initPrime()
{m = 0;for(ll i = 2; i < N; i++){if(!vis[i])prim[m++] = i;for(ll j = i*i; j < N; j += i)vis[j] = true;}
}
int main()
{initPrime();int T;ll n, ans, c;scanf("%d", &T);for(int kase = 1; kase <= T; kase++){scanf("%lld", &n);ans = 1;for(int i = 0; i < m; i++){if(ll(prim[i])*prim[i] > n)break;c = 0;while(n % prim[i] == 0){n /= prim[i];c++;}if(c)ans *= c * 2 + 1;}if(n > 1)ans *= 3;printf("Case %d: %lld\n", kase, ans/2+1);}return 0;
}