CC

自然万物都趋向从有序变得无序

0%

LightOJ 1236 Pairs Forming LCM

发表于 更新于 分类于 Valine：

题目链接:点我

题目

Find the result of the following code:

long long pairsFormLCM( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm means least common multiple
    return res;
}

A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 1014).

Output

For each case, print the case number and the value returned by the function 'pairsFormLCM(n)'.

Sample Input

15

2

3

4

6

8

10

12

15

18

20

21

24

25

27

29

Sample Output

Case 1: 2

Case 2: 2

Case 3: 3

Case 4: 5

Case 5: 4

Case 6: 5

Case 7: 8

Case 8: 5

Case 9: 8

Case 10: 8

Case 11: 5

Case 12: 11

Case 13: 3

Case 14: 4

Case 15: 2

题意:

求前n个数组合的最小公倍数等于n的数有多少组.

思路:

由唯一分解定理我们知道,n = p1e1p_1{^{e1}} * p2e2p_2{^{e2}} * p3e3p_3{^{e3}} …, 那么,根据LCM的性质我们可以知道,两个数的最小公倍数为两个数共有的p中指数e较大的那些数的乘积.然后根据这个性质我们可以把整数n用唯一分解定理拆分,那么我们知道,n的每一个pep^{e} 都必须出现在满足LCM(a, b) = n,的a后者b中,于是这题转化为求排列组合.
假若指数e出现在a中,那么b中的指数有 e + 1 种情况,假若没有出现在a中,那么a有 e 种情况,而b只能取e,所有共有2 * e + 1 种情况,由于题目中要求a <= b,所以我们将答案除以2, 然后加上 a = b 的一种情况.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;

const int maxn = 1e7 + 10;
typedef long long LL;
bool isprime[maxn];
int pri[maxn/10];
int num;

void prime(){
    memset(isprime,false,sizeof(isprime));
    num = 0;
    for(int i = 2; i < maxn; ++i){
        if(!isprime[i]) pri[++num] = i;
        for(int j = 1; j <= num && i * pri[j] < maxn; ++j){
            isprime[i * pri[j]] = true;
            if( i % pri[j] == 0) break;
        }
    }
}

int main(){
    LL n;
    int t;
    prime();
    int kase = 0;
    scanf("%d", &t);
    while(t-- ){
        scanf("%lld", &n);
        LL ans = 1;
        for(int i = 1; i <= num && pri[i] <= (int)sqrt(n); ++i){
            LL cnt = 0;
            while(n % pri[i] == 0){
                n /= pri[i];
                ++cnt;
            }
            ans *= (2 * cnt + 1) ;
        }
        if(n > 1) ans *= 3;
        printf("Case %d: %lld\n",++kase, ans / 2 + 1);
    }
    return 0;
}