Pairs Forming LCM LightOJ - 1236

题意

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

分析

组合数学 ，唯一分解定理,对于每一个素因子 p i , 如果该素因子共有 n u m i 个，则对于该素因子来说 ( a , b ) （ 0 − n u m i , n u m i ) 和 （ n u m i , 0 − n u m i ) ,去掉重复的一个 ( n u m i , n u m i ) 共有 2 ∗ ( n u 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;
}