UVa 10892 - LCM Cardinality

#数学 #分解质因数 #LCM

Published on 2016-02-16

描述

给定正整数 $n(1\le n\le 2000000000)$ ，统计有多少个整数对 $(a, b) (a\le b)$ ，满足 $\text{lcm}(a, b) = n$ 。

样例输入

样例输出

2 2
12 8
24 11
101101291 5

分析

首先我们得明白 $\text{lcm}$ 的一些事情。对于正整数 $a = p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_n^{a_n}, b = p_1^{b_1}p_2^{b_2}p_3^{b_3}...p_n^{b_n}$ ，有：

\text{lcm}(a, b) = p_1^{\max(a_1, b_1)}p_2^{\max(a_2, b_2)}p_3^{\max(a_3, b_3)}...p_n^{\max(a_n, b_n)}

就意味着对于 $\text{lcm}(a, b)$ 的每个 $p_i^{k_i}$ ， $a$ 和 $b$ 的因子 $p_i$ 的指数均不大于 $k_i$ ，但一定有一个的指数等于 $k_i$ 。我们通过确定 $a$ 和 $b$ 的每一个因子 $p_i$ 的指数取值情况，最后得到所有可行的整数对。虽然题目要求 $a \le b$ ，但是单凭一个因数的指数取值无法限制，所以我们先允许重复计算，后面再去除重复。
如果 $a$ 的因子 $p_i$ 的指数是 $k_i$ ， $b$ 的因子 $p_i$ 的指数可以取 $[0, k_i)$ ；如果 $b$ 是 $k_i$ ， $a$ 可以取 $[0, k_i)$ ，加上 $a, b$ 都取 $k_i$ 的情况，一共有 $2\times k_i + 1$ 种情况。
对于每一个 $p_i^{k_i}$ ，都有 $2\times k_i + 1$ 种情况，那么根据乘法原理，每个因数的情况数乘起来就行。但是 $(a, b)$ 被算了两次，而 $(n, n)$ 只被算了一次（它应该被算两次！），所以答案是 $\frac{ans + 1}{2}$ ，又因为答案是奇数，所以也写作： $\left\lfloor\frac{ans}{2} \right\rfloor + 1$ 。
剩下的就是分解质因数，并且运用了线性筛法，不会的自行百度，注意我们只试到 $\left\lfloor \sqrt{n}\right\rfloor$

代码

//  Created by Sengxian on 2/16/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10892 数学 分解质因数 LCM
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 45000 + 3;
bool isPrime[maxn];
vector<int> primes;

void sieve() {
    fill(isPrime, isPrime + maxn, true);
    for(int i = 2; i < maxn; ++i) {
        if(isPrime[i]) primes.push_back(i);
        for(int j = 0; j < primes.size() && i * primes[j] < maxn; ++j) {
            isPrime[i * primes[j]] = false;
            if(i % primes[j] == 0) break;
        }
    }
}

int n;

int main() {
    sieve();
    while(n = ReadInt(), n) {
        printf("%d ", n);
        int s = sqrt(n), ans = 1;
        for(int i = 0; i < primes.size() && primes[i] <= s; ++i) {
            int cnt = 0;
            while(n % primes[i] == 0) cnt++, n /= primes[i];
            ans *= cnt * 2 + 1; //a 或 b 有一个为 cnt，另一取 0 - cnt 。所以有 cnt * 2 + 1 种情况！
        }
        if(n > 1) ans *= 3; //大质数
        printf("%d\n", ans / 2 + 1); //(x, x) 只算了一次，ans 是奇数故直接 / 2 
    }
    return 0;
}

附加输入

附加输出

2 2
12 8
1000000 85
12345676 68
87675612 23
1251562 41
9412 23
6537 5
123 5
12 8
3244 8
56342 41
1233 8
344333 14
98123 2
1 1
2 2
3 2
243 6
123999 5

UVa 11038 - How Many O's? UVa 662 - Fast Food

Sengxian's Blog