Tìm Số Có N Ước (NDIVISORS)

Nguồn: LQDOJ Độ khó: Khá Số học Đếm ước Đệ quy Quy hoạch động

Đề bài

NDIVISORS – Tìm số có n ước

Giới hạn thời gian: 2.0 giây. Giới hạn bộ nhớ: 256 MB.

Cho số nguyên dương $n$. Gọi $s$ là số nguyên dương nhỏ nhất có chính xác $n$ ước (ở đây ta chỉ tính ước dương).

Yêu cầu: Cho số nguyên dương $n$. In ra $s$ (biết rằng: đề ra đảm bảo $s \le 10^{18}$).

Input: Một dòng duy nhất chứa số nguyên $n$ $(1 \le n \le 1000)$.

Output: In ra $s$ cần tìm.

Test 1 – input

2

Test 1 – output

2

Giải thích: Đáp án là $2$ vì $2$ là số nguyên dương nhỏ nhất có chính xác $2$ ước (dương).

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bài này đề rất ngắn nhưng có rất nhiều cách làm: từ vét cạn, quay lui (đệ quy không trả về), đệ quy có trả về, đệ quy có nhớ, quy hoạch động bottom-up cho tới rút gọn còn mảng 1 chiều. Anh em cứ từ từ đọc từng phần nha.

Tóm tắt đề bài một cách đơn giản nhất: bạn hãy tìm số nguyên dương nhỏ nhất (gọi là $s$) có chính xác $n$ ước (chỉ tính ước dương), với $1 \le n \le 1000$ và đề đảm bảo $s \le 10^{18}$.

• Ví dụ 1: $n = 2$ thì $s = 2$. Số $2$ có 2 ước là $\{1, 2\}$, và nó cũng là số nhỏ nhất có 2 ước.
• Ví dụ 2: $n = 4$ thì $s = 6$. Số $6$ có 4 ước là $\{1, 2, 3, 6\}$; các số nhỏ hơn $1, 2, 3, 4, 5$ lần lượt chỉ có $1, 2, 2, 3, 2$ ước, nên $6$ là số nhỏ nhất có 4 ước.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn từng s · TLECách 2Quay lui trên số mũ · ACCách 3Đệ quy có trả về · ACCách 4Đệ quy có nhớ · ACCách 5QHĐ bottom-upCách 6Tham khảo: mảng 1 chiều

Cách 1Vét cạn: thử từng số s và đếm ước

Cách làm đơn giản nhất của bài này chính là vét cạn, tức là thử mọi trường hợp có thể. Đề đảm bảo $s \le 10^{18}$ và ta cần tìm số nhỏ nhất, vậy ta làm một vòng lặp cho $s$ chạy từ 1 lên, với mỗi $s$ ta đếm số ước của nó. Số đầu tiên có đúng $n$ ước chính là đáp án, vì ta đang duyệt từ bé đến lớn mà.

Để đếm số ước của một số, ta dùng cách phân tích thừa số nguyên tố với độ phức tạp $O(\sqrt{N})$: thử chia cho $i = 2, 3, \ldots$ chừng nào $i \cdot i \le N$, đếm xem $N$ chia hết cho $i$ bao nhiêu lần (cnt), rồi nhân kết quả với $(cnt + 1)$. Cuối cùng nếu $N$ còn lại khác 1 thì đó là một số nguyên tố lớn, nhân thêm 2. Vì sao lại nhân $(cnt + 1)$ thì mình giải thích kỹ ở cách 2 nha.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

int cntDivisors(ll n){
    int res = 1;
    for(ll i = 2; i * i <= n; ++i){
        int cnt = 0;
        while(n % i == 0){
            cnt++;
            n /= i;
        }
        if(cnt){
            res *= (cnt + 1);
        }
    }
    if(n != 1){
        res *= 2;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    ll s = 1;
    while(s <= (ll)1e18){
        if(cntDivisors(s) == n){
            break;
        }
        s++;
    }
    cout << s;
    return 0;
}

def cntDivisors(n):
    res = 1
    i = 2
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        if cnt:
            res *= (cnt + 1)
        i += 1
    if n != 1:
        res *= 2
    return res

n = int(input())
s = 1
while s <= 10**18:
    if cntDivisors(s) == n:
        break
    s += 1
print(s)

C++▶ Chạy tay từng dòng codeCách 1: s chạy từ 1, mỗi s đếm số ước bằng cntDivisors (O(√s)), gặp số có đúng n ước thì dừng.

Dữ liệu vào (stdin) – sửa thoải mái2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6int cntDivisors(ll n){

7 int res = 1;

8 for(ll i = 2; i * i <= n; ++i){

9 int cnt = 0;

10 while(n % i == 0){

11 cnt++;

12 n /= i;

13 }

14 if(cnt){

15 res *= (cnt + 1);

16 }

17 }

18 if(n != 1){

19 res *= 2;

20 }

21 return res;

22}

23

24int main(){

25 ios::sync_with_stdio(0);

26 cin.tie(0);

27 int n;

28 cin >> n;

29 ll s = 1;

30 while(s <= (ll)1e18){

31 if(cntDivisors(s) == n){

32 break;

33 }

34 s++;

35 }

36 cout << s;

37 return 0;

38}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: $O(s \cdot \sqrt{s})$ với $s$ là đáp án. Hàm cntDivisors() tốn $O(\sqrt{N})$; vẫn còn cách đếm ước nhanh hơn với $O(\sqrt[3]{N})$ (có bài viết trên blog Codeforces, entry 22317), nhưng nó khá phức tạp và cũng không giúp ta giải được bài này.

Không gian$O(1)$

Thời gian$O(s\sqrt{s})$

TLE chắc chắn

Dù cntDivisors() là $O(\sqrt{N})$ hay $O(\sqrt[3]{N})$ thì ta vẫn bị TLE, vì nếu đáp án $s$ lên tới gần $10^{18}$ thì vòng while phải chạy từ 1 tới tận đó. Mình đo thử bản C++: $n = 512$ (đáp án $17\,297\,280$) đã mất khoảng 36 giây. Tuy nhiên hãy vẫn nên cài đặt nó để lấy làm công cụ kiểm tra tính chính xác cho cách tối ưu trên các test nhỏ nha.

Cách 2Quay lui trên số mũ của 9 số nguyên tố đầu tiên

Tính chất đếm ước

Với số $N \ge 2$ bất kỳ, ta đều phân tích được thành thừa số nguyên tố: $N = p_1^{q_1} \cdot p_2^{q_2} \cdots p_k^{q_k}$ với $p_1, p_2, \ldots, p_k$ là các số nguyên tố phân biệt và $q_1, \ldots, q_k$ là số mũ. Khi đó số ước dương của $N$ là:

Công thức số ước

$d(N) = (q_1 + 1) \cdot (q_2 + 1) \cdots (q_k + 1)$
Vì mỗi ước của $N$ có dạng $p_1^{a_1} \cdots p_k^{a_k}$ với $0 \le a_t \le q_t$, tức số mũ $a_t$ có $q_t + 1$ cách chọn.

$100 = 2^2 \cdot 5^2$ ⇒ $(2+1)(2+1) = $ 9 ước

$12 = 2^2 \cdot 3^1$ ⇒ $(2+1)(1+1) = $ 6 ước

Ta cần tìm $s = p_1^{q_1} \cdots p_k^{q_k}$ có $n$ ước, tức là $(q_1 + 1)(q_2 + 1) \cdots (q_k + 1) = n$. Từ đây phải trả lời câu hỏi: với $n$ tối đa ($n = 1000$) thì cần tối đa bao nhiêu số nguyên tố?

Chỉ cần 9 số nguyên tố đầu tiên

Số mũ càng bé thì ta càng dùng được nhiều số nguyên tố. Để dùng nhiều số nguyên tố nhất thì mọi số mũ bằng 1, lúc đó $n = 2 \cdot 2 \cdots 2 = 2^k$. Với $n \le 1000$: $2^9 = 512$ ước còn được, $2^{10} = 1024$ đã vượt 1000 mất rồi. Nói cách khác, một số mà phân tích thừa số nguyên tố dùng tới 10 số nguyên tố thì có ít nhất $2^{10} = 1024$ ước, quá $1000$. Vậy tối đa 9 số nguyên tố là đủ.

Và vì ta cần $s$ nhỏ nhất, nên 9 số nguyên tố đó cũng phải là 9 số nguyên tố nhỏ nhất:

235711131719232931

Ví dụ một số có 3 ước có thể là $9 = 3^2$, nhưng số nhỏ nhất là $4 = 2^2$. Một số có 512 ước có thể là $3 \cdot 5 \cdot 7 \cdots 29$, nhưng thay vì thế lấy $2 \cdot 3 \cdot 5 \cdots 23$ cũng có 512 ước mà nhỏ hơn. (Còn số nhỏ nhất có 512 ước là $17\,297\,280 = 2^7 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11 \cdot 13$.)

Kết luận

$s = 2^{q_1} \cdot 3^{q_2} \cdot 5^{q_3} \cdots 23^{q_9}$ với $(q_1 + 1)(q_2 + 1) \cdots (q_9 + 1) = n$. Việc của ta là vét cạn mọi bộ số mũ $q_1, \ldots, q_9$ để tạo ra các số có $n$ ước, rồi lấy số nhỏ nhất.

Minh hoạ: tách n thành tích các (q + 1)

Mỗi cách viết $n$ thành tích các thừa số $\ge 2$ cho ta một ứng viên: thừa số $(q + 1)$ lớn nhất gán cho số mũ của $2$, thừa số lớn tiếp theo cho $3$, … (số mũ lớn thì nên đặt cho số nguyên tố nhỏ). Em nhập $n$ rồi bấm Tiếp để xem từng ứng viên và số nhỏ nhất được chọn ra:

n

Ví dụ nhanh:

Bấm n = 12: có 4 cách là $12$, $6 \cdot 2$, $4 \cdot 3$, $3 \cdot 2 \cdot 2$, tương ứng $2^{11} = 2048$, $2^5 \cdot 3 = 96$, $2^3 \cdot 3^2 = 72$, $2^2 \cdot 3 \cdot 5 = 60$. Số nhỏ nhất là 60.

Hàm quay lui Try(i, val, cnt)

Ở cách này ta tạo ra hàm đệ quy không trả về cho tiện, gọi là Try(). Vì nó không trả về nên cần một biến toàn cục res lưu kết quả – số nhỏ nhất có $n$ ước tìm được tới hiện tại. Lúc đầu chưa biết nó bằng bao nhiêu nên cứ khởi tạo bằng giá trị lớn nhất có thể là $10^{18}$ (đề đảm bảo kết quả $\le 10^{18}$). Mảng p lưu 9 số nguyên tố đầu tiên, quy định p[1] = 2, …, p[9] = 23, còn p[0] cho bằng 0 cho đủ chỗ.

• Tham số: i – đang xét số nguyên tố thứ $i$; val – giá trị của số đã tạo ra được; cnt – số ước của val.
• Điều kiện dừng:
  1. cnt > n: số ước đã vượt $n$, không hợp lệ, return.
  2. cnt == n: đúng trường hợp cần tìm, cập nhật res = min(res, val) rồi return.
  3. i > 9: đã dùng hết 9 số nguyên tố mà vẫn chưa đủ ước, return.
• Xử lý chạy: thử mọi số mũ $j = 1, 2, \ldots$ cho p[i]: mỗi vòng nhân val *= p[i] (vòng 1 là nhân $p_i^1$, vòng 2 thành $p_i^2$, …) rồi gọi Try(i + 1, val, cnt * (j + 1)), vì nhân thêm $p_i^j$ thì số ước được nhân $(j + 1)$. Điều kiện lặp: số định tạo ra không được vượt quá res (ta đang tìm số nhỏ hơn res mà), tức val * p[i] <= res.

Coi chừng tràn số khi so sánh val * p[i] <= res

Lúc đầu res = 10^18; nếu val gần $10^{18}$ và p[i] = 23 thì val * p[i] $\approx 2.3 \cdot 10^{19}$, trong khi long long chỉ chứa tới $2^{63} - 1 \approx 9.2 \cdot 10^{18}$ (kể cả unsigned long long cũng chỉ tới $\approx 1.8 \cdot 10^{19}$). Vậy thay vì kiểm val * p[i] <= res, ta kiểm val <= res / p[i] – hai điều kiện tương đương với số nguyên dương mà không bao giờ tràn. Mẹo chung: muốn kiểm a * b <= c mà a * b có thể tràn thì hãy kiểm a <= c / b.

Kết quả: gọi Try(1, 1, 1) (bắt đầu từ số nguyên tố thứ 1, giá trị 1, số 1 có 1 ước), cuối cùng in res. Source code để các bạn tham khảo:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

ll n, res = (ll)1e18;
ll p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

void Try(int i, ll val, int cnt){
    if(cnt > n){
        return;
    }
    if(cnt == n){
        res = min(res, val);
        return;
    }
    if(i > 9){
        return;
    }
    for(int j = 1; val <= res / p[i]; ++j){
        val *= p[i];
        Try(i + 1, val, cnt * (j + 1));
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    Try(1, 1, 1);
    cout << res;
    return 0;
}

n = int(input())
res = 10**18
p = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23]

def Try(i, val, cnt):
    global res
    if cnt > n:
        return
    if cnt == n:
        res = min(res, val)
        return
    if i > 9:
        return
    j = 1
    while val <= res // p[i]:
        val *= p[i]
        Try(i + 1, val, cnt * (j + 1))
        j += 1

Try(1, 1, 1)
print(res)

Trong khung chạy tay, để ý vòng for dừng rất sớm khi res đã nhỏ – đó chính là "cắt tỉa" giúp cách này chạy nhanh:

C++▶ Chạy tay từng dòng codeCách 2: Try(i, val, cnt) thử mũ j = 1, 2, … cho p[i] khi val ≤ res / p[i], đủ n ước thì cập nhật res.

Dữ liệu vào (stdin) – sửa thoải mái2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6ll n, res = (ll)1e18;

7ll p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

8

9void Try(int i, ll val, int cnt){

10 if(cnt > n){

11 return;

12 }

13 if(cnt == n){

14 res = min(res, val);

15 return;

16 }

17 if(i > 9){

18 return;

19 }

20 for(int j = 1; val <= res / p[i]; ++j){

21 val *= p[i];

22 Try(i + 1, val, cnt * (j + 1));

23 }

24}

25

26int main(){

27 ios::sync_with_stdio(0);

28 cin.tie(0);

29 cin >> n;

30 Try(1, 1, 1);

31 cout << res;

32 return 0;

33}

ChậmVừaNhanhRất nhanh

Cách này tốn bao nhiêu phép tính?

Đánh giá độ phức tạp cách này khá khó. Nhưng mình có thể thêm một biến tmp đếm số lần lặp trong hàm Try(), rồi thử mọi $n$ từ 1 đến 1000 để tìm $n$ tốn nhiều phép tính nhất, kèm đo thời gian:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, res = (ll)1e18;
ll p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};
int tmp;

void Try(int i, ll val, int cnt){
    if(cnt > n) return;
    if(cnt == n){
        res = min(res, val);
        return;
    }
    if(i > 9) return;
    for(int j = 1; val <= res / p[i]; ++j){
        tmp++;
        val *= p[i];
        Try(i + 1, val, cnt * (j + 1));
    }
}

int main(){
    int calc = 0, x;
    for(int i = 1; i <= 1000; ++i){
        clock_t start = clock();
        n = i;
        res = (ll)1e18;
        tmp = 0;
        Try(1, 1, 1);
        if(tmp > calc){
            calc = tmp;
            x = i;
        }
        double timeUse = (double)(clock() - start) / CLOCKS_PER_SEC;
        cout << i << " " << fixed << setprecision(5) << timeUse << endl;
    }
    cout << x << endl << calc;
    return 0;
}

Kết quả: $n$ tốn nhiều phép tính nhất là $n = 993$, với 188 694 phép tính, xấp xỉ $2 \cdot 10^5$ – quá nhẹ, AC thoải mái. Có một điều rất hay: chạy code AC với $n = 993$ sẽ in ra $10^{18}$, trong khi $10^{18}$ chỉ có 361 ước, vậy chương trình sai sao? Không đâu: vì không tồn tại số nào $\le 10^{18}$ có 993 ước. $993 = 3 \cdot 331$, nên để có 993 ước thì các (số mũ + 1) phải là $993$ hoặc $(331, 3)$; số nhỏ nhất có 993 ước là $2^{330} \cdot 3^2$, lớn hơn $10^{18}$ rất rất nhiều (em bấm nút "n = 993" ở khung minh hoạ phía trên để xem). Chương trình ta chỉ đảm bảo đúng khi đáp án $\le 10^{18}$, và đề cũng đảm bảo như vậy.

Không gian$O(9)$ tầng đệ quy

Thời gian≈ $2 \cdot 10^5$ phép tính (tệ nhất)

Cách 3Đệ quy có trả về: Try(i, n)

Ở bài này ta có thể làm nhiều cách hơn nữa, chẳng hạn biến hàm Try() thành hàm có trả về, từ đó tiến tới quy hoạch động top-down rồi bottom-up. Ý tưởng: một hàm cho ta biết số nhỏ nhất có $n$ ước với điều kiện chỉ dùng các số nguyên tố nằm trong $i$ số nguyên tố đầu tiên.

• Hàm: long long Try(i, n) trả về số nhỏ nhất có $n$ ước khi xét $i$ số nguyên tố đầu tiên.
• Điều kiện dừng:
  1. $n = 1$: số nhỏ nhất có 1 ước chính là $1$, trả về $1$.
  2. Tới đây số ước cần tạo khác 1. Nếu $n = 0$ (số có 0 ước) hoặc $i = 0$ (không được dùng số nguyên tố nào) thì số đó không tồn tại, trả về giá trị không hợp lệ. Vì ta đang tìm min nên giá trị không hợp lệ là một số rất lớn: LLONG_MAX $= 2^{63} - 1$.
• Xử lý chạy: gọi res là kết quả của Try(i, n), có 2 trường hợp:
  1. Không dùng số nguyên tố thứ $i$: res = Try(i - 1, n).
  2. Có dùng p[i] với số mũ $j$: đặt mul $= p_i^j$, thử $j = 1, 2, \ldots$ với 2 điều kiện: $(j + 1) \le n$ (dùng $p_i^j$ thì có ít nhất $j + 1$ ước) và $p_i^j \le 10^{18}$ (viết chống tràn là mul <= maxVal / p[i] trước khi nhân). Thêm nữa, $n$ phải chia hết cho $(j + 1)$ thì $p_i^j$ mới góp mặt được. Khi đó phần còn lại là số nhỏ nhất có $n / (j + 1)$ ước dùng $i - 1$ số nguyên tố đầu: tmp = Try(i - 1, n / (j + 1)), ứng viên là tmp * mul nếu không vượt $10^{18}$ (kiểm chống tràn tmp <= maxVal / mul).

Công thức đệ quy

$\text{Try}(i, n) = \min\Big(\text{Try}(i-1, n),\ \min_{(j+1) \mid n} \text{Try}\big(i-1, \tfrac{n}{j+1}\big) \cdot p_i^{\,j}\Big)$. Đáp án: $\text{Try}(9, n)$, vì số cần tìm chỉ dùng các số nguyên tố trong 9 số đầu tiên.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

ll Try(int i, int n){
    if(n == 1){
        return 1;
    }
    if(n == 0 || i == 0){
        return LLONG_MAX;
    }
    ll res = Try(i - 1, n), mul = 1;
    for(int j = 1; (j + 1) <= n && mul <= (maxVal / p[i]); ++j){
        mul *= p[i];
        if(n % (j + 1) == 0){
            ll tmp = Try(i - 1, n / (j + 1));
            if(tmp <= maxVal / mul){
                res = min(res, tmp * mul);
            }
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    cout << Try(9, n);
    return 0;
}

LLONG_MAX = 2**63 - 1
maxVal = 10**18
p = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23]

def Try(i, n):
    if n == 1:
        return 1
    if n == 0 or i == 0:
        return LLONG_MAX
    res = Try(i - 1, n)
    mul = 1
    j = 1
    while (j + 1) <= n and mul <= maxVal // p[i]:
        mul *= p[i]
        if n % (j + 1) == 0:
            tmp = Try(i - 1, n // (j + 1))
            if tmp <= maxVal // mul:
                res = min(res, tmp * mul)
        j += 1
    return res

n = int(input())
print(Try(9, n))

C++▶ Chạy tay từng dòng codeCách 3: Try(i, n) = min(không dùng p[i], dùng p[i]^j với (j+1) | n), không nhớ gì.

Dữ liệu vào (stdin) – sửa thoải mái2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

7

8ll Try(int i, int n){

9 if(n == 1){

10 return 1;

11 }

12 if(n == 0 || i == 0){

13 return LLONG_MAX;

14 }

15 ll res = Try(i - 1, n), mul = 1;

16 for(int j = 1; (j + 1) <= n && mul <= (maxVal / p[i]); ++j){

17 mul *= p[i];

18 if(n % (j + 1) == 0){

19 ll tmp = Try(i - 1, n / (j + 1));

20 if(tmp <= maxVal / mul){

21 res = min(res, tmp * mul);

22 }

23 }

24 }

25 return res;

26}

27

28int main(){

29 ios::sync_with_stdio(0);

30 cin.tie(0);

31 int n;

32 cin >> n;

33 cout << Try(9, n);

34 return 0;

35}

ChậmVừaNhanhRất nhanh

Với cách làm trên ta cũng AC được bài này luôn rồi (mình đo bản C++ với mọi $n$ từ 1 tới 1000, lâu nhất chỉ khoảng 0.02 giây). Nhưng để ý ô "đỏ" trong khung chạy tay: nhiều Try(i, n) bị tính lại – ta còn cải tiến được.

Cách 4Đệ quy có nhớ (quy hoạch động top-down)

Code ở cách 3 chưa tối ưu về thời gian vì một vấn đề đã tính rồi mà lần sau gặp lại vẫn phải tính lại. Tư tưởng của đệ quy có nhớ là dùng một kiểu dữ liệu (mảng, vector, map, …) để lưu những kết quả đã tính, gặp lại thì chỉ việc trả về. Ta làm 3 bước:

1. Tham số nào thay đổi khi gọi đệ quy? Cả $i$ và $n$. Vậy ta dùng mảng 2 chiều $F$ với $F[i][n]$ lưu kết quả Try(i, n).
2. Giới hạn của các tham số? $i \le 9$ (tối đa 9 số nguyên tố) và $n \le 1000$. Vậy khai báo f[9 + 5][1000 + 5]; mình thường cộng thêm 5 để thừa ra vài phần tử, tránh truy cập ra ngoài mảng.
3. Giá trị hàm không thể trả về? Try(i, n) không bao giờ trả về $0$ (số 0 có vô số ước, hàm không thiết kế để trả về nó). Vậy mảng $F$ toàn số 0 (khai báo toàn cục là tự có) nghĩa là "chưa tính". Sau điều kiện dừng, nếu f[i][n] != 0 thì trả về luôn; ngược lại tính như bình thường, lưu vào f[i][n] rồi trả về.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};
ll f[9 + 5][1000 + 5];

ll Try(int i, int n){
    if(n == 1){
        return 1;
    }
    if(n == 0 || i == 0){
        return LLONG_MAX;
    }
    if(f[i][n]){
        return f[i][n];
    }
    ll res = Try(i - 1, n), mul = 1;
    for(int j = 1; (j + 1) <= n && mul <= (maxVal / p[i]); ++j){
        mul *= p[i];
        if(n % (j + 1) == 0){
            ll tmp = Try(i - 1, n / (j + 1));
            if(tmp <= maxVal / mul){
                res = min(res, tmp * mul);
            }
        }
    }
    return f[i][n] = res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    cout << Try(9, n);
    return 0;
}

LLONG_MAX = 2**63 - 1
maxVal = 10**18
p = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23]
f = [[0] * (1000 + 5) for _ in range(9 + 5)]

def Try(i, n):
    if n == 1:
        return 1
    if n == 0 or i == 0:
        return LLONG_MAX
    if f[i][n]:
        return f[i][n]
    res = Try(i - 1, n)
    mul = 1
    j = 1
    while (j + 1) <= n and mul <= maxVal // p[i]:
        mul *= p[i]
        if n % (j + 1) == 0:
            tmp = Try(i - 1, n // (j + 1))
            if tmp <= maxVal // mul:
                res = min(res, tmp * mul)
        j += 1
    f[i][n] = res
    return res

n = int(input())
print(Try(9, n))

C++▶ Chạy tay từng dòng codeCách 4: như cách 3 nhưng lưu Try(i, n) vào f[i][n], gặp lại thì trả về luôn.

Dữ liệu vào (stdin) – sửa thoải mái4

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

7ll f[9 + 5][1000 + 5];

8

9ll Try(int i, int n){

10 if(n == 1){

11 return 1;

12 }

13 if(n == 0 || i == 0){

14 return LLONG_MAX;

15 }

16 if(f[i][n]){

17 return f[i][n];

18 }

19 ll res = Try(i - 1, n), mul = 1;

20 for(int j = 1; (j + 1) <= n && mul <= (maxVal / p[i]); ++j){

21 mul *= p[i];

22 if(n % (j + 1) == 0){

23 ll tmp = Try(i - 1, n / (j + 1));

24 if(tmp <= maxVal / mul){

25 res = min(res, tmp * mul);

26 }

27 }

28 }

29 return f[i][n] = res;

30}

31

32int main(){

33 ios::sync_with_stdio(0);

34 cin.tie(0);

35 int n;

36 cin >> n;

37 cout << Try(9, n);

38 return 0;

39}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(i_{max} \cdot N)$ với $i_{max} = 9$ là số thứ tự của số nguyên tố lớn nhất phải dùng.
• Thời gian: $O\big(i_{max} \cdot N \cdot (\log_2 maxVal + \log_3 maxVal + \ldots + \log_{23} maxVal)\big)$. Với mỗi cặp $(i, n)$ vòng for chạy tối đa tới khi $p_i^j \le maxVal$, tức $j \le \log_{p_i} maxVal$. Thay $i_{max} = 9$, $N = 1000$, và tổng các log xấp xỉ $220$, ta được cỡ $9 \cdot 1000 \cdot 220 \approx 2 \cdot 10^6$ phép tính – AC chắc chắn. Thực tế còn ít hơn nhiều vì vòng for còn bị chặn bởi $(j + 1) \le n$ và chỉ những giá trị là ước của $n$ mới được gọi tới.

Không gian$O(9 \cdot N)$

Thời gian$\approx 2 \cdot 10^6$ phép tính

Cách 5Đọc thêm: quy hoạch động bottom-up

Đã có top-down thì cũng có bottom-up, chính là anh em tạo ra công thức truy hồi. Cho ae nào đã biết cơ bản về quy hoạch động thì ta có 4 bước:

1Bài toán con: $F[i][j]$ là số nhỏ nhất có $j$ ước khi xét $i$ số nguyên tố đầu tiên.

2Bài toán cơ sở: $F[0][j] = $ LLONG_MAX; $F[i][0] = $ LLONG_MAX, $F[i][1] = 1$.

3Đáp án: $F[9][n]$.

4Truy hồi: $F[i][j] = \min\big(F[i-1][j],\ F[i-1][j/(k+1)] \cdot p_i^k\big)$.

Bước 2: Bài toán cơ sở

Khi không xét số nguyên tố nào ($i = 0$) thì không tạo ra được số nào có $j$ ước (trừ $j = 1$, số 1 không cần số nguyên tố nào). Đơn giản nhất ta lấp từ $F[0][0]$ đến $F[0][n]$ bằng giá trị không hợp lệ LLONG_MAX bằng fill(&f[0][0], &f[0][n + 1], LLONG_MAX); (bạn nào chưa biết hàm fill thì dùng vòng for cũng được, độ phức tạp như nhau). Tiếp theo với mọi $i$: $F[i][0] = $ LLONG_MAX (0 ước là không hợp lệ), $F[i][1] = 1$ (số nhỏ nhất có 1 ước là 1) – lúc này $F[0][1]$ cũng được gán lại thành 1.

Bước 4: Công thức truy hồi

1. Không dùng số nguyên tố thứ $i$: $F[i][j] = F[i-1][j]$.
2. Có dùng $p_i^k$ (đổi tên số mũ thành $k$ vì $i, j$ đã dùng làm biến lặp): thử mọi $k$ với $(k + 1) \le j$ và mul $= p_i^k \le maxVal$ (kiểm chống tràn mul <= maxVal / p[i] trước khi nhân). Cần $j$ chia hết cho $(k + 1)$, và lấy số nhỏ nhất có $j / (k + 1)$ ước dùng $i - 1$ số nguyên tố trước đó nhân với mul, miễn không vượt $maxVal$ (kiểm f[i - 1][j / (k + 1)] <= maxVal / mul).

Công thức truy hồi

$F[i][j] = F[i-1][j]$; rồi với mỗi $k$ thoả $j \bmod (k+1) = 0$ và $F[i-1][j/(k+1)] \le maxVal / mul$: $F[i][j] = \min\big(F[i][j],\ F[i-1][j/(k+1)] \cdot mul\big)$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};
ll f[9 + 5][1000 + 5];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    fill(&f[0][0], &f[0][n + 1], LLONG_MAX);
    for(int i = 0; i < 10; ++i){
        f[i][0] = LLONG_MAX;
        f[i][1] = 1;
    }
    for(int i = 1; i < 10; ++i){
        for(int j = 2; j <= n; ++j){
            f[i][j] = f[i - 1][j];
            ll mul = 1;
            for(int k = 1; (k + 1) <= j && mul <= (maxVal / p[i]); ++k){
                mul *= p[i];
                if(j % (k + 1) == 0 && f[i - 1][j / (k + 1)] <= maxVal / mul){
                    f[i][j] = min(f[i][j], f[i - 1][j / (k + 1)] * mul);
                }
            }
        }
    }
    cout << f[9][n];
    return 0;
}

LLONG_MAX = 2**63 - 1
maxVal = 10**18
p = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23]

n = int(input())
f = [[LLONG_MAX] * (n + 1) for _ in range(10)]
for i in range(10):
    f[i][0] = LLONG_MAX
    f[i][1] = 1
for i in range(1, 10):
    for j in range(2, n + 1):
        f[i][j] = f[i - 1][j]
        mul = 1
        k = 1
        while (k + 1) <= j and mul <= maxVal // p[i]:
            mul *= p[i]
            if j % (k + 1) == 0 and f[i - 1][j // (k + 1)] <= maxVal // mul:
                f[i][j] = min(f[i][j], f[i - 1][j // (k + 1)] * mul)
            k += 1
print(f[9][n])

C++▶ Chạy tay từng dòng codeCách 5: lấp bảng f[i][j] theo từng hàng i = 1..9, mỗi ô thử mọi số mũ k của p[i].

Dữ liệu vào (stdin) – sửa thoải mái4

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

7ll f[9 + 5][1000 + 5];

8

9int main(){

10 ios::sync_with_stdio(0);

11 cin.tie(0);

12 int n;

13 cin >> n;

14 fill(&f[0][0], &f[0][n + 1], LLONG_MAX);

15 for(int i = 0; i < 10; ++i){

16 f[i][0] = LLONG_MAX;

17 f[i][1] = 1;

18 }

19 for(int i = 1; i < 10; ++i){

20 for(int j = 2; j <= n; ++j){

21 f[i][j] = f[i - 1][j];

22 ll mul = 1;

23 for(int k = 1; (k + 1) <= j && mul <= (maxVal / p[i]); ++k){

24 mul *= p[i];

25 if(j % (k + 1) == 0 && f[i - 1][j / (k + 1)] <= maxVal / mul){

26 f[i][j] = min(f[i][j], f[i - 1][j / (k + 1)] * mul);

27 }

28 }

29 }

30 }

31 cout << f[9][n];

32 return 0;

33}

ChậmVừaNhanhRất nhanh

Với cách trên độ phức tạp không gian và thời gian vẫn như cách top-down, nhưng không tốn thời gian và bộ nhớ cho việc gọi đệ quy nữa; nhìn vào code cũng dễ tính ra độ phức tạp thời gian hơn: 3 vòng lặp lồng nhau $9 \times N \times$ (tối đa khoảng $\log_{p_i} maxVal$).

Không gian$O(9 \cdot N)$

Thời gian$O(9 \cdot N \cdot 60)$

Cách 6Tham khảo: rút gọn còn mảng 1 chiều

Ta hoàn toàn có thể rút gọn từ mảng 2 chiều thành mảng 1 chiều, giúp tiết kiệm bộ nhớ và chạy nhanh hơn (truy cập mảng 1 chiều nhanh hơn 2 chiều); còn độ phức tạp thời gian thì vẫn như cách trên.

Bỏ [i] khỏi $F[i][j]$, chỉ còn $F[j]$: số nhỏ nhất có $j$ ước. Bài toán cơ sở: fill(f, f + n + 1, LLONG_MAX); rồi f[1] = 1. Để dễ hình dung: ô nào chưa xét tới thì là của quá khứ (hàng $i - 1$), ô nào đã xét thì là của hiện tại (hàng $i$).

• $F[i][j] = F[i-1][j]$ thành $F[j] = F[j]$: không cần làm gì nữa.
• $F[i][j] = \min(F[i][j], F[i-1][j/(k+1)] \cdot mul)$ thành $F[j] = \min(F[j], F[j/(k+1)] \cdot mul)$. Nếu vẫn cho $j$ chạy xuôi thì $F[j/(k+1)]$ (chỉ số nhỏ hơn $j$) đã bị cập nhật ở hàng $i$ rồi, trong khi ta cần hàng $i - 1$. Giải pháp: cho vòng for(j) chạy ngược từ $n$ về 2. Khi đó $F[j/(k+1)]$ chưa bị xét tới, vẫn là của quá khứ, tức đúng $F[i-1][j/(k+1)]$.

Giống bài cái túi (knapsack)

Đây cũng chính là mẹo quen thuộc khi rút gọn bài cái túi 0/1 về mảng 1 chiều: ô cần dùng nằm ở chỉ số nhỏ hơn thì duyệt ngược để nó vẫn còn là giá trị của "hàng trước".

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};
ll f[1005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    fill(f, f + n + 1, LLONG_MAX);
    f[1] = 1;
    for(int i = 1; i < 10; ++i){
        for(int j = n; j >= 2; --j){
            ll mul = 1;
            for(int k = 1; (k + 1) <= j && mul <= (maxVal / p[i]); ++k){
                mul *= p[i];
                if(j % (k + 1) == 0 && f[j / (k + 1)] <= maxVal / mul){
                    f[j] = min(f[j], f[j / (k + 1)] * mul);
                }
            }
        }
    }
    cout << f[n];
    return 0;
}

LLONG_MAX = 2**63 - 1
maxVal = 10**18
p = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23]

n = int(input())
f = [LLONG_MAX] * (n + 1)
f[1] = 1
for i in range(1, 10):
    for j in range(n, 1, -1):
        mul = 1
        k = 1
        while (k + 1) <= j and mul <= maxVal // p[i]:
            mul *= p[i]
            if j % (k + 1) == 0 and f[j // (k + 1)] <= maxVal // mul:
                f[j] = min(f[j], f[j // (k + 1)] * mul)
            k += 1
print(f[n])

C++▶ Chạy tay từng dòng codeCách 6: chỉ giữ f[j], j chạy ngược để f[j/(k+1)] vẫn là giá trị của hàng i - 1.

Dữ liệu vào (stdin) – sửa thoải mái4

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6const ll maxVal = (ll)1e18, p[10] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23};

7ll f[1005];

8

9int main(){

10 ios::sync_with_stdio(0);

11 cin.tie(0);

12 int n;

13 cin >> n;

14 fill(f, f + n + 1, LLONG_MAX);

15 f[1] = 1;

16 for(int i = 1; i < 10; ++i){

17 for(int j = n; j >= 2; --j){

18 ll mul = 1;

19 for(int k = 1; (k + 1) <= j && mul <= (maxVal / p[i]); ++k){

20 mul *= p[i];

21 if(j % (k + 1) == 0 && f[j / (k + 1)] <= maxVal / mul){

22 f[j] = min(f[j], f[j / (k + 1)] * mul);

23 }

24 }

25 }

26 }

27 cout << f[n];

28 return 0;

29}

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời gian$O(9 \cdot N \cdot 60)$

Ở bài này thì có khá nhiều cách; trong thực chiến thì ta cứ nghĩ ra được cách nào dễ hiểu, code không quá phức tạp mà AC được là ok rồi nha.

Ghi chú của mình: mình đã chạy cả 6 code C++ và 6 code Python với test đề, rồi so với một chương trình tham chiếu độc lập (liệt kê mọi cách tách $n$ thành tích các thừa số giảm dần, tính bằng số nguyên lớn, không giới hạn $10^{18}$) cho mọi $n$ từ 1 đến 1000 có đáp án $\le 10^{18}$ (517 giá trị) – cách 2 đến 6 khớp hết; chương trình tham chiếu cũng được đối chiếu với sàng đếm ước tới $2 \cdot 10^7$. Cách 1 (vét cạn) khớp với 69 giá trị $n$ có đáp án $\le 2 \cdot 10^5$. Thời gian: cách 2–6 bản C++ đều dưới 0.02 giây với mọi $n$, bản Python lâu nhất khoảng 0.35 giây (cách 3). Với $n$ không có đáp án $\le 10^{18}$ (như 993, 997 – đề đảm bảo không có trong test) thì cách 2 in $10^{18}$, còn cách 3–6 in LLONG_MAX. Mình cũng đã chạy lại code đếm phép tính ở trên và ra đúng $n = 993$ với $188\,694$ phép tính.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇