LightOJ - 1236 (唯一分解定理)

题意：求有多少对数对(i,j)满足lcm(i,j) = n，1<=i<=j, 1<=n<=1e14。

分析：根据整数的唯一分解定理，n可以分解为(p1^e1)*(p2^e2)*(p3^e3)*...*(pn^en)。其中pi是每个不同的素因子。

同样可将 i 和 j 分解为(a1^c1)*(a2^c2)^(a3^c3)...(an^cn) 和 (b1^d1)*(b2^d2)*(b3^d3)*...(bn^dn)。

因为lcm(i,j) = n。所以对任意 i，都有max(ci,di)= ei ，0 <= min(ci,di) <= ei，所以对n的每个素因子，都有2*(ei+1)-1种情况（减1是因为ci=di=ei的情况被算了2次）。

所有的可能 t 就是 (2ei+1)之积。这是有序对的数量，求无序对的时候 将 (t+1)/2，加1是因为(n,n)的情况本身只有一种可能。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn =1e7+;

const int INF =0x3f3f3f3f;

bool notprime[maxn<<];

vector<int> prime;

  //prime[0] 表示当前范围内有多少素数,prime[i] 表示第i个素数是多少

void pre()

{

    memset(notprime,,sizeof(notprime));

    notprime[] = notprime[] = true;

    for(int i=;i<maxn;++i){

        if(!notprime[i]) prime.push_back(i);

        for(int j= ; j<prime.size() && prime[j] <= maxn / i ;++j){

            notprime[prime[j]*i] = true;

            if(i%prime[j]==) break;

        }

    }

}

LL getFactor(LL n)

{

    LL tmp = n , res=;

    for(int i=;i<prime.size() && prime[i]*prime[i]<=tmp;++i){

        int cnt =;

        while(tmp%prime[i]==){

            cnt++;

            tmp/=prime[i];

        }

        res *=(*cnt + );

    }

    if(tmp>) res*= ;

    res++;

    res>>=;

    return res;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    pre();

    int T,N,u,v,tmp,cas=;

    scanf("%d",&T);

    while(T--){

        LL n; scanf("%lld",&n);

        LL res= getFactor(n);

        printf("Case %d: %lld\n",cas++,res);

    }

    return ;

}