原题网址：http://www.bnuoj.com//problem_show.php?pid=13155

首先我们需要知道一个简单的数论知识 就是唯一分解定理 一个数可以分解成多个素数相乘
如果
a=p1 ^ a1 * p2 ^ a2 *…*pn ^ an
b=p1 ^ b1 * p2 ^ b2 *…*pn ^ bn
(其中pi表示素因子 ai 和bi表示素因子的个数)
则有
gcd(a,b)=p1 ^ min(a1,b1) * p2 ^ min(a2,b2) …pn ^ min(an,bn) — (1)
lcm(a,b)=p1 ^ max(a1,b1) * p2 ^ max(a2,b2) …pn ^ max(an,bn) —(2)

这里说下我对式子1 和式子2的理解：
首先 gcd 的值一定是a和b的因子 那么为什么要取最小的质因数个数呢？如果a有5个3 b有3个3 要保证gcd能整除a和b 又因为是最大公约数 所以就取较小的那个数的全部 也就是3个3
关于lcm呢 首先是最小公倍数 也就是一定能被a和b整除 那么怎么保证被整除呢 比如a有5个3
b有3个3 那么你的lcm起码得有5个3相乘吧？ 不然是不能被a整除的

这里举个例子 比如：
12=2 ^ 2 * 3 ^1
18=2 ^ 1 * 3 ^ 2
那么
gcd(12,18)=2 ^ min(1,2) * 3 ^ min(1,2)=6
lcm(12,18)=2 ^ max(1,2) * 3 ^ max(1,2)=36

知道了上面的前置技能后 就可以做这个题了
因为是多组 所以我们先预处理出来所有的素数 题中n到1e14
先把1e6以内的素数筛出来
lcm(a,b)=p1 ^ e1 * p2 ^ e2 *…*pn ^en
又由上面的知识可以知道
e1=max(a1,b1) e2=max(a2,b2) … en=max(an,bn)
当ai=ei 时候 bi可以取[0,ei] 有ei+1种情况 当bi=ei的时候 也一样 也就是 2 * ei+2种情况
当ai=bi=ei时候 只有一种情况 算重复了 所以 对于每个质因数 有2 * ei+1种情况
除了(n,n)的情况 所有的情况都出现了两次 (因为最开始的ai和bi是无序的)
满足a<=b的情况 所以结果是 ( ∏(2 * ei+1) / 2 ） +1 ( ∏的意思代表乘积 )

这里举个例子吧
比如ei=2
那么当ai=2时候 bi=0、1、2，当bi=2时候 ai=0、1、2
但因为刚开始没去算ai和bi的大小问题 所以就6个 所以最后要除以2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7+5;
int  prime[N/10],tot;
bool vis[N];
int main()
{
    for(ll i=2; i<N; i++)
        if(!vis[i])
        {
            prime[tot++]=i;
            for(ll j=i*i; j<N; j+=i)
                vis[j]=1;
        }
    int t;
    cin>>t;
    for(int cas=1; cas<=t; cas++)
    {
        ll n;
        cin>>n;
        ll t=n;
        ll ans=1;
        for(int i=0; i<tot&&prime[i]*prime[i]<=n; i++)
        {
            ll cnt=0;
            while(t%prime[i]==0)
                cnt++,t/=prime[i];
            ans*=(2*cnt+1);
        }

        if(t>1) ans*=3;
        printf("Case %d: %lld\n",cas,ans/2+1);
    }
    return 0;
}