Tích Các Ước (MULDIV)
Đề bài
MULDIV – Tích các ước
Giới hạn thời gian: 1.0 giây. Giới hạn bộ nhớ: 1023 MB. Nhập/xuất chuẩn (bàn phím, màn hình).
Cho 1 số nguyên dương $n$ là tích của $m$ số nguyên tố ($m$ số nguyên tố này không nhất thiết phải khác nhau). Ta có $n = p_1 \times p_2 \times \ldots \times p_m$.
Yêu cầu: Hãy tìm tích các ước của $n$.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên dương $m$ $(m \le 200000)$.
- Dòng tiếp theo gồm $m$ số nguyên tố $p_i$ $(2 \le p_i \le 200000,\ \forall i: 1 \le i \le m)$.
Kết quả: Phần dư của tích các ước của số $n$ khi chia cho $10^9 + 7$.
2
2 3363
2 3 21728Lờ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 😇. Mình cảnh báo trước: code thì ngắn thôi, nhưng bài này động đến khá nhiều toán đó, các bạn có nháp thì lôi nháp ra sẵn đi nha 🤣.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
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 OJTrước tiên mình tóm tắt lại đề bài một cách đơn giản nhất cho bạn nào chưa hiểu: cho $m$ ($m \le 2 \cdot 10^5$) số nguyên tố $p[i]$ ($2 \le p[i] \le 2 \cdot 10^5$). Số nguyên dương $n$ là tích của $m$ số nguyên tố đó: $n = p[1] \cdot p[2] \cdot \ldots \cdot p[m]$. Hãy tìm phần dư của tích tất cả các ước của $n$ khi chia cho $10^9 + 7$.
Ví dụ $m = 2$, $p = \{2, 3\}$. Suy ra $n = 2 \cdot 3 = 6$, các ước của $6$ là $\{1, 2, 3, 6\}$, tích các ước $= 1 \cdot 2 \cdot 3 \cdot 6 = 36$, và $36 \bmod (10^9 + 7) = 36$. Vậy kết quả là $36$.
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ính n rồi tìm hết các ước – O(√n)
Cách đơn giản nhất để giải bài này chính là vét cạn thôi, làm y như đề bài bảo: tính $n$, rồi tìm tất cả các ước số của $n$, nhân vào và chia dư là có kết quả. Để tối ưu nhất thì ở bước tìm ước ta làm với độ phức tạp $O(\sqrt{n})$: chỉ cho $i$ chạy từ $1$ tới $\sqrt{n}$, hễ $i$ là ước thì $j = n / i$ cũng là ước (một ước $\le \sqrt{n}$ luôn đi kèm một ước $\ge \sqrt{n}$). Nhớ là khi $i = j$ (tức $i = \sqrt{n}$, $n$ là số chính phương) thì chỉ nhân một lần thôi 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;
const ll mod = (ll)1e9 + 7;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> m;
vector<ll> p(m);
ll n = 1;
for(int i = 0; i < m; ++i) {
cin >> p[i];
n *= p[i];
}
ll res = 1;
for(ll i = 1; i * i <= n; ++i) {
if(n % i == 0) {
ll j = n / i;
res *= i;
res %= mod;
if(j != i) {
res *= j;
res %= mod;
}
}
}
cout << res;
return 0;
}mod = 10**9 + 7
m = int(input())
p = list(map(int, input().split()))
n = 1
for i in range(m):
n *= p[i]
res = 1
i = 1
while i * i <= n:
if n % i == 0:
j = n // i
res = res * i % mod
if j != i:
res = res * j % mod
i += 1
print(res)Giải thích 1 số chỗ trong code:
ios::sync_with_stdio(0); cin.tie(0);giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé). Bài nào cần nhập xuất nhiều – như bài này có tới $2 \cdot 10^5$ số – thì nên thêm vào để chạy nhanh hơn.vector<ll> p(m): khai báo 1 vector có $m$ phần tử, để lúc đọc chỉ việccin >> p[i]thôi.i * i <= n: chính là $i \le \sqrt{n}$ đó, nhưng ta bình phương 2 vế lên để tránh việcsqrt(n)làm tròn số thực, nhỡ có khả năng lỗi.res %= mod: ở đây ta áp dụng đồng dư thức. Dành cho bạn nào chưa biết thì $(a \cdot b) \bmod M = \big((a \bmod M) \cdot (b \bmod M)\big) \bmod M$. Vậy thay vì nhân hết vào rồi mới chia dư (sẽ bị tràn số), cứ mỗi lần nhân ta lại chia dư luôn.
long long rồi ⇒ tràn số ⇒ WA (Wrong Answer). Mình thử với $m = 200000$ số $2$: $n$ bị tràn thành $0$, vòng lặp không chạy lần nào và chương trình in ra $1$ 😅. Với $20$ số nguyên tố đầu tiên ($n \approx 5.6 \cdot 10^{26}$) thì in ra $969181912$ trong khi đáp án đúng là $966315100$. Mà kể cả không tràn thì riêng việc đi tìm hết ước của một số cỡ $10^{18}$ đã cần $10^9$ vòng lặp – TLE (Time Limit Exceeded) rồi nha các bạn.Cách trên không thể AC (Accepted) được bài này. Tuy nhiên vẫn nên cài đặt nó để sau này lấy làm công cụ kiểm tra tính chính xác cho cách làm tối ưu. Chỉ lưu ý là khi dùng nó để đối chiếu thì cho chạy những test bé thôi, vì $n$ to là tràn số, chính cách vét cạn sẽ sai đó.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(m)$ cho mảng $p$.
- Thời gian: $O(m + \sqrt{n})$ – mà $n$ có thể khổng lồ (tới $200000^{200000}$), nên coi như không dùng được.
Cách 2Công thức tích các ước, Fermat nhỏ và lũy thừa nhanh – O(m + k·log)
Giờ ta đến cách làm tối ưu để AC bài này nha. Cho tiện viết công thức, ở phần này mình gọi số $n$ là $a$, và gọi số lượng ước của $a$ là $b$. Cả bài sẽ đi qua mấy chặng như sau:
Chặng 1: Ghép cặp các ước
Ta đi từ ví dụ cho dễ hình dung nhé. Giả sử $a = 12$, các ước của nó là $\{1, 2, 3, 4, 6, 12\}$. Tích các ước số của $a$ là:
= (1 × 12) × (2 × 6) × (3 × 4) (đảo chỗ một chút)
= 12 × 12 × 12 = 123 = 1728
Các bạn thấy quy luật rồi chứ. Để mình lý giải cho: với số nguyên dương $a$ có $b$ ước mà $b$ chẵn, nếu có một ước $x \lt \sqrt{a}$ thì cũng có một ước $y = a / x \gt \sqrt{a}$, và $x \cdot y = a$. Vì $b$ chẵn nên có đúng $b / 2$ cặp như vậy. Ở ví dụ trên số $12$ có $6$ ước thì có $3$ cặp là $(1 \cdot 12)$, $(2 \cdot 6)$, $(3 \cdot 4)$. Tích các ước số của $a$ = tích các cặp, mà mỗi cặp bằng $a$ và có $b / 2$ cặp nên:
Với $b$ lẻ thì sao nhỉ? Có một quy luật là chỉ những số chính phương mới có số lượng ước lẻ – xuống dưới phần cách tìm $b$ mình sẽ chứng minh, tạm thời cứ coi nó đúng đi. Giả sử $a = 25$, các ước của nó là $\{1, 5, 25\}$. Tích các ước số là:
= (1 × 25) × 5
= (1 × 25) × 250.5 (^0.5 chính là căn bậc hai đó)
= 251.5 (vì ab × ac = ab + c)
= (52)1.5 = 53 = 125 (vì (ab)c = ab × c)
Với số chính phương thì vẫn có các cặp $x \cdot y = a$, nhưng vì số lượng ước lẻ nên sẽ có đúng 1 ước là $\sqrt{a}$ không ghép được với ước nào khác (chỉ có $\sqrt{a} \cdot \sqrt{a} = a$ thôi mà). Nên có $(b - 1) / 2$ cặp, ở ví dụ trên là $1$ cặp $(1 \cdot 25)$. Vậy tích các ước của $a$ là:
$a^{\frac{b-1}{2}} \cdot \sqrt{a} = a^{\frac{b-1}{2}} \cdot a^{\frac{1}{2}} = a^{\frac{b}{2} - \frac{1}{2} + \frac{1}{2}} = a^{\frac{b}{2}}$
Vậy là kể cả $b$ lẻ thì tích các ước số của $a$ vẫn $= a^{b/2}$. Nhưng lưu ý ở đây $b / 2$ không làm tròn đâu nha, ở ví dụ trên là $25^{3/2} = 25^{1.5} = 125$ đó. Để chỉ làm việc với số nguyên dương, ta viết nó thành $\big(a^{1/2}\big)^b = (\sqrt{a})^b$. Vì $a$ là số chính phương nên $\sqrt{a}$ là số nguyên dương.
- $b$ chẵn: kết quả $= a^{b/2}$.
- $b$ lẻ ($a$ chính phương): kết quả $= (\sqrt{a})^{b}$.
Minh hoạ ghép cặp ước
Các bạn nhập một số $n$ (nhỏ thôi) rồi bấm Tiếp để xem từng cặp ước $(x, n / x)$ được ghép ra sao, và vì sao tích tất cả các ước lại bằng $n^{d/2}$ ($d$ là số ước):
Chặng 2: Tìm số lượng ước b và nhận ra số chính phương
Vậy làm sao tính $a$, $b$ và phân biệt $a$ có phải số chính phương hay không? Ta vẫn cần đi qua vài phần toán nữa.
Một số nguyên dương $a$ luôn phân tích được ra thừa số nguyên tố, ví dụ $12 = 2^2 \cdot 3^1$. Tổng quát: $a = q_1^{e_1} \cdot q_2^{e_2} \cdot \ldots \cdot q_k^{e_k}$ (giả sử phân tích ra được $k$ số nguyên tố khác nhau). Và có một điều thú vị là số ước của $a$:
Ví dụ số ước của $12 = 2^2 \cdot 3^1$ là $(2 + 1) \cdot (1 + 1) = 6$ ước.
(Lý do: mỗi ước của $a$ có dạng $q_1^{x_1} \cdots q_k^{x_k}$ với $0 \le x_i \le e_i$, mỗi số mũ $x_i$ có $e_i + 1$ cách chọn.)
Giờ chứng minh điều "chỉ số chính phương mới có số ước lẻ" nè. Số chính phương là số có căn bậc 2 là số nguyên dương, mà $\sqrt{a} = q_1^{e_1/2} \cdot q_2^{e_2/2} \cdots q_k^{e_k/2}$ nguyên thì các số mũ $e_1, e_2, \ldots, e_k$ đều phải chẵn (chỉ có mũ nguyên mới ra số nguyên). Khi đó $e_1 + 1, e_2 + 1, \ldots, e_k + 1$ đều lẻ, mà lẻ nhân lẻ thì ra lẻ ⇒ số ước của số chính phương là số lẻ. Còn nếu $a$ không phải số chính phương thì khi phân tích ra sẽ có một số nguyên tố có mũ lẻ, ví dụ $3^5$ chẳng hạn, thì khi tính số ước phải nhân với $(5 + 1) = 6$ – một số chẵn – nên số ước chắc chắn chẵn.
Ta tạo một mảng đếm cnt[x] để đếm số lần số nguyên tố $x$ xuất hiện (chính là số mũ), đồng thời lưu các số nguyên tố khác nhau vào vector v để tiện tính toán. Lúc này bài toán từ $a = p[1] \cdot p[2] \cdots p[m]$ đưa về:
$a = v[1]^{cnt[v[1]]} \cdot v[2]^{cnt[v[2]]} \cdots v[k]^{cnt[v[k]]}, \qquad b = (cnt[v[1]] + 1) \cdot (cnt[v[2]] + 1) \cdots (cnt[v[k]] + 1)$
Các bạn nghĩ đến đây là xong chưa? Tất nhiên là chưa rồi 😆. Nó khó hơn ở chỗ $b$ cũng hoàn toàn có thể tràn số: giả sử $a$ là tích của $70$ số nguyên tố khác nhau thì $b = 2^{70}$. Vậy là cả $a$ lẫn $b$ đều có thể tràn số kìa. Nên ta sẽ áp dụng đồng dư thức và vài kiến thức thêm về modulo để giải quyết.
Chặng 3: Tính ab mod M khi cả a và b đều khổng lồ
Giờ ta xét $a^b \bmod M$ ($M = 10^9 + 7$) với $a$, $b$ rất lớn. Ta viết nó thành $(a \cdot a \cdot \ldots \cdot a) \bmod M$ (có $b$ thừa số $a$).
Xử lý $a$ trước. Theo đồng dư thức:
$a^b \bmod M = \big((a \bmod M) \cdot (a \bmod M) \cdots (a \bmod M)\big) \bmod M = (a \bmod M)^b \bmod M \qquad (1)$
Giờ xử lý $b$. Để xử lý được $b$ ta cần biết định lý Fermat nhỏ: "Nếu $M$ là số nguyên tố và $a$ là số nguyên không chia hết cho $M$ thì $a^{M-1} - 1$ chia hết cho $M$", hay viết là $a^{M-1} \bmod M = 1$.
Ta gom $b$ thừa số $a$ thành từng nhóm $M - 1$ thừa số:
$a^b = \underbrace{a^{M-1} \cdot a^{M-1} \cdots a^{M-1}}_{\lfloor b / (M-1) \rfloor \text{ nhóm}} \cdot a^{x}, \qquad x = b \bmod (M - 1)$
(Ở đây $b / (M - 1)$ làm tròn xuống như phép chia trong C++ nha, nên nếu $b \lt M - 1$ thì có $0$ nhóm và $x = b$ – vẫn đúng.) Theo đồng dư thức, và vì $M = 10^9 + 7$ là số nguyên tố nên mỗi nhóm $a^{M-1} \bmod M = 1$:
$a^b \bmod M = \big(1 \cdot 1 \cdots 1 \cdot (a^x \bmod M)\big) \bmod M = a^{\,b \bmod (M-1)} \bmod M \qquad (2)$
Từ (1) và (2) suy ra:
Trong quá trình tính, $a$ ta liên tục chia dư cho $M$, còn $b$ ta liên tục chia dư cho $M - 1$ để tránh tràn số.
Chặng 4: Kỹ thuật cài đặt
Lũy thừa nhanh. Tính $a^b \bmod M$ mà chạy 1 vòng for $b$ lần thì rất lâu, nhỡ $b \bmod (M - 1)$ lớn hơn $10^8$ thì chết. Nên ta áp dụng lũy thừa nhị phân (các bạn có thể tham khảo thêm tại VNOI Wiki). Ý tưởng: nếu $b = 0$ thì $a^b = 1$; còn nếu $b \gt 0$ thì $a^b = a^{\lfloor b/2 \rfloor} \cdot a^{\lfloor b/2 \rfloor}$ khi $b$ chẵn, và $a^b = a^{\lfloor b/2 \rfloor} \cdot a^{\lfloor b/2 \rfloor} \cdot a$ khi $b$ lẻ. Dựa vào đó mà đệ quy, độ phức tạp không còn $O(b)$ mà chỉ $O(\log_2 b)$. Trong quá trình đệ quy cứ nhân xong là chia dư (đồng dư thức cho phép nhân).
Xử lý phép chia 2 trong $b / 2$. Nếu $a$ không phải số chính phương thì đáp án là $a^{b/2}$, vậy làm sao tính $(b / 2) \bmod (M - 1)$? Đoạn này phải xử lý khéo, vì dùng nghịch đảo modulo thì vô cùng phức tạp mà còn có thể sai, do $M - 1 = 10^9 + 6$ chia hết cho $2$ (không có nghịch đảo của $2$). Ý tưởng như ví dụ này: $\big((3 \cdot 5 \cdot 4) / 2\big) \bmod 3$ – ta lấy luôn $4 / 2$ để đơn giản hoá thành $(3 \cdot 5 \cdot 2) \bmod 3$. Đơn giản chưa nào 😁. Ở trường hợp $a$ không chính phương thì chắc chắn có một cnt[v[i]] nào đó lẻ, tức là thừa số $(cnt[v[i]] + 1)$ chẵn. Vậy ngay khi gặp số mũ lẻ đầu tiên, thay vì nhân $b$ với $(cnt[v[i]] + 1)$, ta nhân với $(cnt[v[i]] + 1) / 2$. Thế là đã giải quyết xong phép chia 2!
Tính $\sqrt{a}$ khi $a$ chính phương. Ta có $a = v[1]^{cnt[v[1]]} \cdots v[k]^{cnt[v[k]]}$ với mọi cnt chẵn, nên:
$\sqrt{a} = v[1]^{cnt[v[1]]/2} \cdot v[2]^{cnt[v[2]]/2} \cdots v[k]^{cnt[v[k]]/2}$
- $a = v[1]^{cnt[v[1]]} \cdots v[k]^{cnt[v[k]]}$ ($k$ là số các số nguyên tố khác nhau trong $p$).
- $b = (cnt[v[1]] + 1) \cdots (cnt[v[k]] + 1)$.
- $\sqrt{a} = v[1]^{cnt[v[1]]/2} \cdots v[k]^{cnt[v[k]]/2}$.
- $a^b \bmod M = (a \bmod M)^{\,b \bmod (M-1)} \bmod M$.
- $b$ chẵn: kết quả $= a^{b/2}$; $b$ lẻ: kết quả $= (\sqrt{a})^b$.
- Xử lý $(b / 2) \bmod (M - 1)$: gặp
cnt[v[i]]lẻ đầu tiên thì nhân $b$ với $(cnt[v[i]] + 1) / 2$, các thừa số còn lại nhân bình thường.
Thử với ví dụ 2: $p = \{2, 3, 2\}$ ⇒ $v = [2, 3]$, $cnt[2] = 2$, $cnt[3] = 1$. Xét $2$: mũ chẵn, $b = 1 \cdot 3 = 3$, $a_2 = 2^1 = 2$. Xét $3$: mũ lẻ đầu tiên ⇒ không chính phương, $b = 3 \cdot (1 + 1)/2 = 3$. $a_1 = 2^2 \cdot 3 = 12$. Đáp án $= 12^3 = 1728$ ✅. Còn với $p = \{2, 3, 2, 3\}$ ($a = 36$, chính phương): $b = 3 \cdot 3 = 9$, $\sqrt{a} = 2 \cdot 3 = 6$, đáp án $= 6^9 = 10077696$.
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 mod = (ll)1e9 + 7;
int cnt[200005];
ll powMod(ll a, ll b, ll m) {
if(b == 0) {
return (ll)1;
}
ll half = powMod(a, b / 2, m);
half = (half * half) % m;
if(b % 2) {
return (half * (a % m)) % m;
}
return half % m;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> m;
vector<int> v;
while(m--) {
int x;
cin >> x;
if(cnt[x] == 0) {
v.push_back(x);
}
cnt[x]++;
}
bool isSquareNum = true;
ll a1 = 1, a2 = 1, b = 1;
for(int i = 0; i < (int)v.size(); ++i) {
a1 = (a1 * powMod(v[i], cnt[v[i]], mod)) % mod;
if(isSquareNum && cnt[v[i]] % 2) {
isSquareNum = false;
b = (b * ((cnt[v[i]] + 1) / 2)) % (mod - 1);
}
else {
b = (b * (cnt[v[i]] + 1)) % (mod - 1);
}
if(isSquareNum) {
a2 = (a2 * powMod(v[i], cnt[v[i]] / 2, mod)) % mod;
}
}
ll res;
if(isSquareNum) {
res = powMod(a2, b, mod);
}
else {
res = powMod(a1, b, mod);
}
cout << res << endl;
return 0;
}import sys
mod = 10**9 + 7
def powMod(a, b, m):
if b == 0:
return 1
half = powMod(a, b // 2, m)
half = half * half % m
if b % 2:
return half * (a % m) % m
return half % m
data = sys.stdin.buffer.read().split()
m = int(data[0])
cnt = [0] * 200005
v = []
for k in range(1, m + 1):
x = int(data[k])
if cnt[x] == 0:
v.append(x)
cnt[x] += 1
isSquareNum = True
a1, a2, b = 1, 1, 1
for i in range(len(v)):
a1 = a1 * powMod(v[i], cnt[v[i]], mod) % mod
if isSquareNum and cnt[v[i]] % 2:
isSquareNum = False
b = b * ((cnt[v[i]] + 1) // 2) % (mod - 1)
else:
b = b * (cnt[v[i]] + 1) % (mod - 1)
if isSquareNum:
a2 = a2 * powMod(v[i], cnt[v[i]] // 2, mod) % mod
if isSquareNum:
res = powMod(a2, b, mod)
else:
res = powMod(a1, b, mod)
print(res)Giải thích 1 số chỗ trong code:
ll powMod(ll a, ll b, ll m): hàm tính $a^b \bmod m$ bằng lũy thừa nhị phân (ở đây $a$, $b$ đã bé rồi nhé). Vào hàm mình check nếu $b = 0$ thì trả về $1$. Tiếp tới tínhhalf– một nửa, tức $a^{\lfloor b/2 \rfloor}$. Sau đóhalf = (half * half) % mvì dù $b$ lẻ hay chẵn thì đều có $a^{\lfloor b/2 \rfloor} \cdot a^{\lfloor b/2 \rfloor}$, nhớ chia dư cho $m$ để tránh tràn. Cuối cùng nếu $b$ lẻ thì nhân thêm $a$ rồi chia dư rồi trả về, còn $b$ chẵn thì trả thẳnghalf.bool isSquareNum = true;– trong tiếng Anh số chính phương là square number đó các bạn, ban đầu mình đặt biến check số chính phương làtrue.ll a1 = 1, a2 = 1, b = 1:a1chính là $a$, còna2chính là $\sqrt{a}$. Mình cố tình gộp 2 trường hợp chính phương và không chính phương lại để chạy trong 1 vòng for nên hơi khó hiểu chút.if(isSquareNum && cnt[v[i]] % 2): nếu cócnt[v[i]]lẻ thì chứng tỏ $a$ không phải số chính phương, ta đổi biến check vềfalse; và vìcnt[v[i]] + 1chẵn nên lấy $b \cdot \big((cnt[v[i]] + 1) / 2\big)$ rồi chia dư cho $M - 1$. Nhờ bước này mà từ đoạn sau ta chỉ việc nhân tiếp như bình thường, việc chia 2 ở $b / 2$ đã được giải quyết rồi.else { b = (b * (cnt[v[i]] + 1)) % (mod - 1); }: nếucnt[v[i]]chẵn, hoặc đã gánisSquareNum = falserồi, thì những lần sau luôn chạy vàoelsenày để tính $b$ như bình thường.a2chỉ được tính khiisSquareNumvẫn còntruenha.- Đoạn cuối tách 2 trường hợp:
isSquareNumđúng thì tínha2$^b \bmod M$, sai thì tínha1$^b \bmod M$. Lưu ý tuy là cùng 1 biến $b$ nhưng ở 2 trường hợp nó khác hẳn nhau: nếu đã chạy vàoif(isSquareNum && cnt[v[i]] % 2)thì $b$ chỉ nhân với $(cnt[v[i]] + 1) / 2$ ở thừa số đó – và chỉ chạy vào đúng 1 lần thôi, vì sau lần đầuisSquareNumđã thànhfalse.
pow(a, b, m) tính lũy thừa nhanh có chia dư, nhưng ở trên mình vẫn viết lại powMod y như bản C++ để các bạn đối chiếu. Số nguyên của Python không bị tràn, nhưng nếu nhân thẳng $n$ ra thì số sẽ có cả triệu chữ số – chậm vô cùng – nên vẫn phải làm theo công thức như trên nhé.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(m + \max p_i)$ cho mảng đếm
cnt(kích thước $2 \cdot 10^5$) và vectorv. - Thời gian: đọc và đếm mất $O(m)$; với mỗi số nguyên tố khác nhau ($k \le m$) gọi powMod mất $O(\log cnt)$; cuối cùng 1 lần powMod với số mũ $\lt 10^9 + 6$ mất khoảng $30$ bước. Tổng cộng $O(m + k \log m + \log M)$ – coi như $O(m)$.
Các bạn có thể thấy code thì không hề dài tí nào, nhưng để lý giải ra hoàn toàn thì vô cùng dài đúng không 😅.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét