題目： UVa - 11960 - Divisor Game

題目說明

給一個整數 N，求小於等於 N 的正整數中，因數最多的數字，若有相同則取較大者。

Input： 第一個整數 T，表示有 T 組測資，後面 T 行每行都有一個整數，代表 N。

Output： 輸出小於等於 N 的正整數中，因數最多的數字，若有相同則取較大者。

解題思路

解法一:

想知道每個數字的因數個數，可以使用一個數組保存並初始化為 1，因為每個數都至少有一個因數，接著遍歷陣列，將所有數字的倍數都加一，最後就可以得到所有數的因數個數，最後根據題目的要求更新數組並輸出答案即可。

解法二:

一個正整數的所有因數其實都是該數質因數的組合 ( 可參考本篇文章: 演算法課程題解 - 基礎數論 3 - HackMD )，因此要知道該數因數的個數，需要先做質因數分解，可以先使用質數篩 ( 可參考本篇文章: 演算法筆記 - Prime )，找出每個數的最小質因數，接著遍歷陣列，將數字不斷除以自己的最小質因數即可完成質因數分解。接著根據題目的要求更新數組並輸出答案即可。

參考解法

解法一

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 <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fxmaAx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int maxN = (int)1e6 + 1;

int N;
int ans[maxN];

void preProcessing()
{
    for (int i = 1; i < maxN; ++i) for (int j = i; j < maxN; j += i) ++ans[j];

    int n = 2, _max = ans[2];
    for (int i = 3; i < maxN; ++i)
    {
        if (ans[i] >= _max) _max = ans[i], n = i;
        ans[i] = n;
    }
}

void solve()
{
    int T, tmp;
    cin >> T;
    while (T--)
    {
        cin >> tmp;
        cout << ans[tmp] << '\n';
    }
}

int main()
{
    preProcessing();
    solve();
}

解法二

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>

using namespace std;

/*
reference:
    https://hackmd.io/@SCIST/BasicMath3#UVa-11960
    質數篩: http://web.ntnu.edu.tw/~algo/Prime.html#3
*/

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int maxN = (int)1e6 + 1;

int N;
int prime[maxN];  // 紀錄每個數字的最小質因數
int ans[maxN];

void preProcessing()
{
    // 質數篩
    for (long long i = 2; i < maxN; ++i)
    {
        if (prime[i]) continue;

        prime[i] = (int)i;
        for (long long j = i * i; j < maxN; j += i)
            if (!prime[j]) prime[j] = (int)i;
    }

    // 計算每個數的因數個數，找出每個質因數的最大次方，可能性就是最大次方加一 ( 可不選 )
    fill(ans, ans + maxN, 1);
    for (int i = 2; i < maxN; ++i)
    {
        int tmp = i;
        while (tmp != 1)
        {
            int p = prime[tmp], cnt = 0;
            while (!(tmp % p)) tmp /= p, ++cnt;
            ans[i] *= ++cnt;
        }
    }

    int n = 2, _max = ans[2];
    for (int i = 3; i < maxN; ++i)
    {
        if (ans[i] >= _max) _max = ans[i], n = i;
        ans[i] = n;
    }
}

void solve()
{
    int T, tmp;
    cin >> T;
    while (T--)
    {
        cin >> tmp;
        cout << ans[tmp] << '\n';
    }
}

int main()
{
    preProcessing();
    solve();
}

參考資料

範例程式碼 uva11960
演算法課程題解 - 基礎數論 3 - HackMD
演算法筆記 - Prime