一開始用暴力法(直接1~n找每個數的因數數量):

long long n;
    cin >> n;
    int Max=0,Max_index=0;
    for(long long i=1;i<=n;i++){
        int N=sqrt(i);
        int total=0;
        for(int j=1;j<=N;j++){
            if(i%j==0){
                if(i / j != j)total+=2;
                else total+=1;
            }
        }
        if(total>Max){
            Max=total;
            Max_index=i;
        }
        cout << i << ". " << total << endl;
    }
    cout << Max_index << " " << Max;

可想而知的TLE了

 

接下來我想到可以用質數篩+質因數分解+約數公式

質數篩的部分 我一開始是用埃氏篩，後來又被TLE後，我以為是篩法的問題，於是改成用線性篩，結果我又又又被TLE了

 

然後我就很破防地去問gpt到底要怎麼解

底下這個就是gpt給我的最終解

然後我沒學過DFS所以我看不懂:(

 

p.s : gpt給的那個prime陣列不夠 因為題目測資真的太大了 所以要用到41才夠

🎯 目標回顧

輸入一個整數 n，你要找出：

• 哪個數 i ∈ [1, n] 的約數個數最多

• 並印出 i 和它的約數個數

🧠 背後數學概念：約數個數公式

任何正整數都能表示為：

n = p₁^e₁ * p₂^e₂ * ... * pₖ^eₖ

其中 p₁, p₂, ..., pₖ 是不同的質數。

則：

約數個數 = (e₁ + 1) * (e₂ + 1) * ... * (eₖ + 1)

🧠 思路逆轉：不再「枚舉所有數」！

前兩種方法都是：

• 每個 i = 1 到 n 都算一次 → 慢

現在反過來想：

直接枚舉所有可能的質因數組合，試著用小質數湊出不超過 n 的數，並記住約數最多的那個。

✅ 做法分解步驟

第一步：列出小質數

通常只需要 2, 3, 5, 7, 11, ... 到 31 左右就夠了。因為越大的質數乘起來會太快超過 n。

vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

第二步：用 DFS 嘗試每種乘法組合

我們會遞迴地做這件事：

1. 選第 idx 個質數 p

2. 決定要用 p^1, p^2, ..., p^k（但總乘積不能超過 n）

3. 每次都更新：

   • 現在的乘積值（即候選數字）

   • 約數個數（每次乘上 (次方 + 1)）

第三步：記錄答案

如果現在這個乘積的「約數個數」比以前多，就更新答案。

✅ 程式架構圖解：

dfs(idx, curr_num, curr_divisors, prev_exp)
    |
    |-- 嘗試 primes[idx]^exp for exp = 1 to prev_exp
    |      |
    |      |-- num *= primes[idx]
    |      |-- divisor_count *= (exp + 1)
    |      |-- dfs(idx + 1, num, divisor_count, exp)

prev_exp 限制：質因數次方要遞減或相等（避免重複組合，像 2^2 * 3^1 和 3^1 * 2^2）

✅ 最終完整程式碼

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

ll n;  // 輸入的最大值
ll best_num = 1;
int max_div_cnt = 1;

vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};

void dfs(int idx, ll curr, int div_cnt, int prev_exp) {
    if (curr > n) return;

    if (div_cnt > max_div_cnt || (div_cnt == max_div_cnt && curr < best_num)) {
        max_div_cnt = div_cnt;
        best_num = curr;
    }

    if (idx >= primes.size()) return;

    ll base = primes[idx];
    for (int exp = 1; exp <= prev_exp; ++exp) {
        if (curr > n / base) break; // 防 overflow
        curr *= base;
        dfs(idx + 1, curr, div_cnt * (exp + 1), exp);
    }
}

int main() {
    cin >> n;
    dfs(0, 1, 1, 64); // 初始值：質數編號0、數字1、約數個數1、最大次方64
    cout << best_num << " " << max_div_cnt << '\n';
}

✅ 小總結：

步驟	概念	實作重點
1	約數個數公式	(次方+1)*(次方+1)...
2	小質數乘法組合	用 DFS 一層層乘上質數
3	範圍限制（不超過 n）	curr > n / base
4	降次順序控制避免重複組合	exp <= prev_exp
5	更新最大值	儲存約數最多時的數字