Pairs Forming LCM LightOJ - 1236

Pairs Forming LCM LightOJ - 1236

题意

问共有多少组数的最大公倍数是n

分析

组合数学 ，唯一分解定理,对于每一个素因子 pi $p_i$, 如果该素因子共有 numi $nu{m}_i$个，则对于该素因子来说 (a,b) $(a,b)$ （0−numi,numi) $（0-nu{m}_i,nu{m}_i)$ 和 （numi,0−numi) $（nu{m}_i,0-nu{m}_i)$,去掉重复的一个 (numi,numi) $(nu{m}_i,nu{m}_i)$共有 2∗(numi+1)−1中组合 $2\ast (nu{m}_i+1)-1中组合$

参考代码

int Prime[670000];
const int LEN  = 1e7+1;
bool vis[LEN];
//int Prime[666666];
int cnt = 1;
void init(void)
{
    int n = 1e7;
    for(int i = 2; i <= n; ++i)
    {
        if(!vis[i])
        {
            Prime[cnt++] = i;
            for(LL j = (LL)i +  i; j <= n; j += i)
                vis[j] = 1;
        }

    }
}
int main(void)
{
// const int n = 1e7;
// cout<<n/log(n)<<endl;
    std::ios::sync_with_stdio(false);
    init();
    int T;
    cin>>T;
    int kase = 0;
    while(T--)
    {
        LL n;
        cin>>n;
        int num ;
        LL ans = 1;
        for(int i = 1; i < cnt&& n != 1; ++i)
        {
            if(n%Prime[i]==0)
            {
                num = 0;
                while(n%Prime[i]==0)
                {
                    n /= Prime[i];
                    num++;
                }
                ans *= 2*num+1;//对于某一个质因子来说，共有2（num+1） - 1种选择的方法
            }
        }
        if(n!=1)
            ans *= 3;
        ans = ans/2 + 1;//将重复的除去，并把（n,n) 这种情况给加上
        printf("Case %d: %lld\n",++kase,ans);
    }
    return 0;
}