LightOJ 1236 Pairs Forming LCM(唯一分解定理 )

题目链接

题目大意

  问有多少对i,j满足(lcm(i,j)=n(ileq j))

解题思路

  两个数字的最大公因数其实是两个数所有的质因数都取两者之中最大幂次的结果。假设lcm(i,j)=n,如果a的某个质因数最大幂次是k，那么b的这个质因数取值范围就是0~k，共有k+1种方法，同样的如果b的最大幂次是k，a的这个质因数也有k+1种取法，又因为两者同为k的情况被多计算了一次，所以对于这个质因数两个数一共有2k+1种取法。而根据乘法原理，所有的可能就是各个质因数的取法之积。但是我们之前还没有考虑两个数的大小关系，除了两个数同为n的情况，其他情况既包含大于的关系也包含小于的关系，最后的结果要除以2并向上取整。

代码

const int maxn = 1e7+10;
int t, p[maxn/10]; ll n;
bool u[maxn];
int main() {
    for (int i = 2; i<maxn; ++i) {
        if (!u[i]) p[++p[0]] = i;
        for (int j = 1; i*p[j]<maxn; ++j) {
            u[i*p[j]] = true;
            if (i%p[j]==0) break;
        }
    }
    int t, kase = 1; scanf("%d", &t);
    while(t--) {
        ll n; scanf("%lld", &n);
        ll ans = 1;
        for (int i = 1; (ll)p[i]*p[i]<=n && i<p[0]; ++i)
            if (n%p[i]==0) {
                int cnt = 0;
                while(n%p[i]==0) {
                    ++cnt;
                    n/=p[i];
                }
                ans *= 2*cnt+1;
            }
        if (n>1) ans *= 3;
        printf("Case %d: %lld
", kase++, (ans+1)/2);
    }
    return 0;
}