Arithmetic

Phần dư và chia hết

Với số nguyên $a$ và $m > 0$ có đúng một cặp $(q, r)$ thỏa $a = qm + r$ và $0 \le r < m$. Số $r$ là phần dư, viết $r = a \bmod m$; khi $r = 0$ ta nói $a$ chia hết cho $m$, viết $m \mid a$. Ba phép $+$, $-$, $\times$ đi qua phần dư được:

và tương tự cho phép trừ, phép nhân, vì mọi phần chứa $m$ biến mất khi lấy phần dư. Nhờ vậy ta lấy dư sau từng phép tính thay vì dồn tới cuối. Phép chia thì không đi qua được; mục nghịch đảo bên dưới xử lý riêng.

Chỗ vấp đầu tiên nằm ở C++: % cắt thương về phía 0 nên phần dư mang dấu của số bị chia, -7 % 5 bằng -2, trong khi phần dư toán học là $3$. Muốn phần dư luôn trong $[0, m)$ thì viết (a % m + m) % m; phép trừ hai phần dư viết (x - y + m) % m. Chỗ vấp thứ hai là tràn số: tích hai phần dư lên tới $m^2 \approx 10^{18}$ với $m = 10^9 + 7$, vừa long long nhưng chỉ khi thừa số đã là long long. Với $m$ vượt khoảng $3 \cdot 10^9$, nhân trung gian bằng __int128.

Một chi tiết nhỏ mà đáng: khai báo modulo là const. Biết trước số chia, trình biên dịch thay phép chia chậm bằng phép nhân và dịch bit:

Chỉ thêm chữ const, vòng lặp nhanh gấp hơn 3 lần.

Ví dụBước Tới Bội Số

Đề. $t \le 10^4$ bộ $(a, b)$, $a, b \le 10^9$. Mỗi thao tác tăng $a$ thêm 1; ít nhất bao nhiêu thao tác để $a$ chia hết cho $b$?

Lời giải. Gọi $r = a \bmod b$. Bội kế tiếp của $b$ không nhỏ hơn $a$ là $a$ nếu $r = 0$, và $a + (b - r)$ nếu $r > 0$. Chỗ dễ sai là in $b - r$ cả khi $r = 0$, cho $b$ thay vì $0$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll t, a, b;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> a >> b;
        ll r = a % b;
        cout << (r == 0 ? 0 : b - r) << '\n';
    }
}

ChạyInput4
8 4
8 5
1 9
999999999 1000000000

Output0
2
8
1

ƯCLN và BCNN

Thuật toán Euclid tính ƯCLN, ký hiệu $\gcd(a, b)$, dựa vào một nhận xét: $d$ chia hết cả $a$ lẫn $b$ khi và chỉ khi $d$ chia hết cả $b$ lẫn $r = a \bmod b$, vì $r = a - qb$ và $a = r + qb$. Hai cặp có cùng tập ước chung, nên

Với $(252, 105)$: $252 = 2 \cdot 105 + 42$, $105 = 2 \cdot 42 + 21$, $42 = 2 \cdot 21$, nên $\gcd = 21$. Hình học của phép tính là lát hình chữ nhật bằng hình vuông lớn nhất có thể, cạnh hình vuông cuối cùng là ƯCLN.

Số bước ít vì phần dư giảm rất nhanh: với $a \ge b$ ta có $a \bmod b < a/2$ (nếu $b \le a/2$ thì phần dư nhỏ hơn $b$, còn nếu $b > a/2$ thì phần dư là $a - b$). Cứ hai bước số lớn giảm ít nhất một nửa, nên có $O(\log \min(a, b))$ bước, khoảng 85 phép chia với giá trị tới $10^{18}$.

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

Bội chung nhỏ nhất, ký hiệu $\operatorname{lcm}(a, b)$, đi theo ƯCLN: khi phân tích ra nguyên tố, $\gcd$ lấy số mũ nhỏ hơn còn $\operatorname{lcm}$ lấy số mũ lớn hơn, nên $\gcd \cdot \operatorname{lcm} = ab$ và $\operatorname{lcm}(a, b) = \frac{a}{\gcd(a, b)} \cdot b$. Chia trước nhân sau là cố ý: mọi số trung gian không vượt kết quả. C++17 có sẵn __gcd và gcd. ƯCLN cả dãy thì gộp dần $g \leftarrow \gcd(g, a_i)$ từ $g = 0$; hai số nguyên dương liên tiếp luôn nguyên tố cùng nhau vì $\gcd(n, n + 1) = \gcd(n, 1) = 1$.

Thừa số và ước

Mọi số $n > 1$ viết được duy nhất thành $n = p_1^{e_1} \cdots p_k^{e_k}$ với $p_i$ nguyên tố đôi một khác nhau. Mọi câu hỏi về ước, về chia hết, về chính phương đều đọc được từ biểu diễn này.

Kiểm tra nguyên tố. Hợp số $n = d \cdot e$ với $1 < d \le e$ thì $d^2 \le n$, nên chỉ cần thử $d = 2, 3, \dots$ trong khi $d^2 \le n$. Viết d * d <= n với long long, đừng qua số thực sqrt. Với $n \le 10^{12}$ là $10^6$ lần chia.

Phân tích thừa số. Chạy đúng vòng lặp ấy, mỗi khi $d$ chia hết số còn lại thì chia sạch và ghi số mũ. Mọi $d$ chia được đều nguyên tố, vì thừa số nguyên tố nhỏ hơn của nó đã bị chia sạch từ trước. Vòng lặp dừng khi $d^2$ vượt số còn lại; lúc đó nếu số còn lại lớn hơn 1 thì nó là một nguyên tố với số mũ 1. Thừa số cuối này hay bị quên. Ví dụ $360 = 2^3 \cdot 3^2 \cdot 5$: chia hết 2 ba lần, 3 hai lần, còn $5$, tới $d = 4$ thì $16 > 5$, thêm $5$.

for (ll d = 2; d * d <= n; d++) {
    if (n % d) continue;
    ll e = 0;
    while (n % d == 0) n /= d, e++;
    p[++k] = d, ex[k] = e;
}
if (n > 1) p[++k] = n, ex[k] = 1;

Đếm ước. Mỗi ước chọn độc lập số mũ từ $0$ tới $e_i$ cho từng nguyên tố, nên số ước của $n$, ký hiệu $\tau(n)$, bằng $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$; $360$ có $4 \cdot 3 \cdot 2 = 24$ ước. Số ước nhỏ hơn $n$ rất nhiều: tối đa 1344 khi $n \le 10^9$, 6720 khi $n \le 10^{12}$. Liệt kê ước: các ước đi theo cặp $(d, n/d)$ với một ước không vượt $\sqrt n$; duyệt $d$ tới căn, lấy cả hai (một lần nếu bằng nhau), rồi sắp xếp. Số ước lẻ chỉ khi $n$ là số chính phương.

Ví dụLũy Thừa Chưa Dùng

Đề. Cho $N \le 10^{12}$. Mỗi thao tác chọn $z = p^e$ ($p$ nguyên tố, $e \ge 1$) chia hết giá trị hiện tại của $N$ và chưa từng được chọn, rồi chia $N$ cho $z$. Tìm số thao tác lớn nhất.

Lời giải. Phân tích $N$ thành tích lũy thừa các số nguyên tố, nguyên tố $p$ có số mũ $E_p$. Các thao tác dùng nguyên tố $p$ chọn các số mũ đôi một khác nhau có tổng không vượt $E_p$, và các nguyên tố không tranh nhau gì, nên bài tách theo từng nguyên tố. Với số mũ $E$, $k$ số nguyên dương phân biệt có tổng ít nhất $1 + 2 + \dots + k$, nên chọn các số mũ $1, 2, 3, \dots$ chừng nào còn đủ là tối ưu. Kiểm với $72 = 2^3 \cdot 3^2$: số mũ 3 cho hai thao tác ($2$ và $4$), số mũ 2 cho một ($3$), tổng 3.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, ans;

void take(ll e) {
    for (ll k = 1; e >= k; k++) {
        e -= k;
        ans++;
    }
}

signed main() {
    cin >> n;
    for (ll d = 2; d * d <= n; d++) {
        if (n % d) continue;
        ll e = 0;
        while (n % d == 0) n /= d, e++;
        take(e);
    }
    if (n > 1) take(1);
    cout << ans << '\n';
}

ChạyInput72

Output3

Sàng Eratosthenes

Cần biết số nào trong $1..N$ là nguyên tố, với $N$ cỡ $10^7$. Thử chia từng số tốn tổng cỡ $N\sqrt N$. Sàng Eratosthenes lật ngược cách hỏi: thay vì mỗi số đi tìm ước, mỗi số nguyên tố tự gạch các bội của nó. Duyệt $p = 2, 3, \dots$; nếu $p$ chưa bị gạch thì $p$ nguyên tố, và gạch $p^2, p^2 + p, \dots$. Bắt đầu từ $p^2$ vì bội $kp$ với $k < p$ đã bị gạch bởi ước nguyên tố của $k$; chỉ cần $p \le \sqrt N$ vì hợp số $x \le N$ có ước nguyên tố không quá $\sqrt N$.

for (ll i = 2; i * i <= n; i++)
    if (!comp[i])
        for (ll j = i * i; j <= n; j += i) comp[j] = true;

Mỗi nguyên tố $p$ gạch khoảng $N/p$ số, cộng lại chỉ cỡ $N \log \log N$ phép, gần như tuyến tính: $N = 10^7$ chừng 50 ms. Mảng bool tốn $N$ byte; bitset hoặc vector<bool> chỉ $N/8$ byte khi $N$ cỡ $10^8$.

Khi $R$ tới $10^9$ nhưng chỉ hỏi trên một đoạn $[L, R]$ ngắn cỡ $10^6$ số, ta sàng đoạn (segmented sieve): dùng các nguyên tố $p \le \sqrt R$, mỗi $p$ gạch từ bội đầu tiên của nó trong đoạn, nhưng không sớm hơn $p^2$.

Ví dụBa Ước Dương

Đề. $n \le 10^5$ số $x_i \le 10^{12}$. Với mỗi số, có đúng ba ước dương không?

Lời giải. $\tau(x) = (e_1 + 1)(e_2 + 1) \cdots = 3$ chỉ khi $x$ có đúng một nguyên tố với số mũ 2, tức $x = p^2$. Vậy cần: $x$ là số chính phương và căn của nó là nguyên tố. Căn tới $10^6$ nên sàng tới $10^6$ một lần, mỗi truy vấn tính căn nguyên đúng rồi tra sàng. Căn số thực có thể lệch một đơn vị ở cỡ $10^{12}$, nên sửa lại bằng hai vòng while.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll M = 1e6;
ll n;
bool comp[M + 5];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    comp[0] = comp[1] = true;
    for (ll i = 2; i * i <= M; i++)
        if (!comp[i])
            for (ll j = i * i; j <= M; j += i) comp[j] = true;
    cin >> n;
    while (n--) {
        ll x;
        cin >> x;
        ll r = sqrtl(x);
        while (r * r > x) r--;
        while ((r + 1) * (r + 1) <= x) r++;
        cout << (r * r == x && !comp[r] ? "YES" : "NO") << '\n';
    }
}

ChạyInput6
4 5 9 16 25 49

OutputYES
NO
YES
NO
YES
YES

Đếm theo bội

Có $q = 10^6$ số $x \le 10^6$, mỗi số cần phân tích. Thử chia từng số tốn tổng cỡ $10^9$. Sàng sẵn $\mathrm{spf}[x]$, ước nguyên tố nhỏ nhất (smallest prime factor) của mọi $x \le M$: duyệt $i$ tăng dần, nếu $\mathrm{spf}[i]$ chưa có thì $i$ nguyên tố và gán $i$ cho mọi bội còn trống. Phân tích $x$ khi đó chỉ là chia liên tiếp cho $\mathrm{spf}[x]$, không quá $\log_2 x$ bước.

for (ll i = 2; i <= M; i++)
    if (!spf[i])
        for (ll j = i; j <= M; j += i)
            if (!spf[j]) spf[j] = i;

Muốn số ước $\tau(x)$ hay tổng các ước $\sigma(x)$ cho mọi $x \le M$ cùng lúc, ta đảo vòng lặp: thay vì hỏi “số $x$ có những ước nào”, hỏi “ước $d$ nằm trong những số nào”, tức các bội $d, 2d, 3d, \dots$. Số phép tính là $M/1 + M/2 + \dots + M/M$, khoảng $1{,}4 \cdot 10^7$ với $M = 10^6$.

Hàm phi Euler $\varphi(n)$ là số các $k$ với $1 \le k \le n$ nguyên tố cùng nhau với $n$, bằng $n (1 - 1/p_1)(1 - 1/p_2) \cdots$, với $p_1, p_2, \dots$ là các ước nguyên tố của $n$. Sàng tương ứng: đặt $\varphi[x] = x$, rồi với mỗi nguyên tố $p$ và mỗi bội $x$ của $p$ thì $\varphi[x] \mathrel{-}= \varphi[x]/p$. Khi $M$ cỡ $10^7$ trở lên, sàng tuyến tính gạch mỗi hợp số đúng một lần bởi ước nguyên tố nhỏ nhất của nó, chạy trong $O(M)$.

Lũy thừa nhanh

Tính $a^b \bmod m$ với $b$ tới $10^{18}$. Viết $b$ ở hệ nhị phân: $13 = 1101_2 = 8 + 4 + 1$ nên $a^{13} = a^8 \cdot a^4 \cdot a$. Các lũy thừa $a^{2^i}$ có từ nhau bằng bình phương, nên chỉ cần khoảng $\log_2 b$ phép bình phương và nhiều nhất $\log_2 b$ phép nhân vào kết quả.

ll power(ll a, ll b, ll m) {
    ll res = 1 % m;
    a %= m;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

Vòng lặp giữ bất biến res * a^b luôn bằng đáp án: $b$ lẻ thì chuyển một thừa số $a$ sang res; rồi $a^b = (a^2)^{b/2}$. Khởi tạo 1 % m vì modulo 1 thì mọi phần dư là 0. Cùng khung “bình phương rồi nhân theo bit” dùng được cho mọi phép nhân kết hợp được, như nhân ma trận để tính Fibonacci chỉ số $10^{18}$ (bài 18).

Nghịch đảo và Fermat

Phép chia không đi qua phần dư: $\frac{12}{4} = 3$, nhưng theo modulo 5 hai số này là $2$ và $4$, và $\frac{2}{4}$ không nguyên. Lối thoát là thay “chia cho $b$” bằng “nhân với nghịch đảo” $b^{-1}$, số mà $b \cdot b^{-1}$ chia cho $m$ dư 1. Từ đây ta viết $x \equiv y \pmod m$ (đọc là $x$ đồng dư $y$ theo modulo $m$) khi $x$ và $y$ có cùng phần dư khi chia cho $m$, nên điều kiện trên là $b \cdot b^{-1} \equiv 1 \pmod m$. Nghịch đảo tồn tại khi và chỉ khi $\gcd(b, m) = 1$ (bài 47); với $m = p$ nguyên tố, mọi $b$ không chia hết cho $p$ đều có.

Định lý Fermat nhỏ: nếu $b$ không chia hết cho $p$ (viết $p \nmid b$) thì $b^{p-1} \equiv 1 \pmod p$. Chứng minh ngắn: các số $b, 2b, \dots, (p-1)b$ đôi một khác phần dư và đều khác $0$, nên là một hoán vị của $1, \dots, p - 1$; nhân tất cả lại rồi giản ước $(p-1)!$. Suy ra

tính bằng lũy thừa nhanh. Để tính tổ hợp $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ cho nhiều câu hỏi, tiền xử lý fact[i] và inv[i] $= (i!)^{-1}$: một lần lũy thừa cho inv[N], rồi đi lùi inv[i - 1] = inv[i] * i. Mỗi câu hỏi $O(1)$. Cách này cần $n < p$ và $p$ nguyên tố.

Fermat còn cho hệ quả: nếu $p \nmid a$ thì

Số mũ chỉ cần biết modulo $p - 1$, không phải modulo $p$. Nhờ đó một số mũ khổng lồ như $b^c$ vẫn xử lý được. Nếu $p \mid a$ thì $a^e \equiv 0$ với mọi $e \ge 1$, công thức không áp dụng.

Ví dụLũy Thừa Hai Tầng

Đề. $q \le 10^5$ bộ $(a, b, c)$ với $0 \le a, b, c \le 10^9$. Tính $a^{b^c} \bmod (10^9 + 7)$, quy ước $0^0 = 1$ ở cả hai tầng.

Lời giải. Số mũ $E = b^c$ có thể có cỡ $10^{10}$ chữ số. Đặt $P = 10^9 + 7$; vì $a < P$, $P \mid a$ chỉ khi $a = 0$. Ba trường hợp: nếu $b = 0$ và $c > 0$ thì $E = 0$, đáp án là $1$ kể cả khi $a = 0$; ngược lại $E \ge 1$, nên $a = 0$ cho $0$; còn lại tính $e = b^c \bmod (P - 1)$ rồi in $a^e \bmod P$. Nếu $e = 0$ trong khi $E \ge 1$ thì $(P-1) \mid E$ và $a^E \equiv 1 = a^0$, vẫn khớp. Lỗi hay gặp nhất là rút gọn số mũ theo $P$ thay vì $P - 1$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll P = 1e9 + 7;
ll q, a, b, c;

ll power(ll a, ll b, ll m) {
    ll res = 1 % m;
    a %= m;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> q;
    while (q--) {
        cin >> a >> b >> c;
        if (b == 0 && c > 0) cout << 1 << '\n';
        else if (a == 0) cout << 0 << '\n';
        else cout << power(a, power(b, c, P - 1), P) << '\n';
    }
}

ChạyInput5
2 3 2
5 0 7
0 0 0
0 2 3
7 10 0

Output512
1
0
0
7

Đếm bằng phần nguyên

Số bội của $d$ trong $1..N$ là $\lfloor N/d \rfloor$. Từ đây có hai công cụ.

Công thức Legendre. Số mũ của nguyên tố $p$ trong $n!$, ký hiệu $v_p(n!)$, là

vì có $\lfloor n/p^i \rfloor$ số $x \le n$ chia hết $p^i$, mỗi số góp một thừa số $p$ cho lũy thừa ấy. $v_5(100!) = 20 + 4 = 24$. Vòng lặp chỉ cần chia dần: for (ll q = n / p; q; q /= p) s += q;.

Gộp khối. Tổng $\lfloor N/1 \rfloor + \lfloor N/2 \rfloor + \dots + \lfloor N/N \rfloor$ với $N = 10^{12}$ có quá nhiều số hạng, nhưng thương $\lfloor N/d \rfloor$ chỉ có $O(\sqrt N)$ giá trị khác nhau: với $d \le \sqrt N$ có không quá $\sqrt N$ giá trị của $d$, còn với $d > \sqrt N$ thương nhỏ hơn $\sqrt N$. Mỗi giá trị chiếm một khối $d$ liên tiếp; khối bắt đầu từ $l$ kết thúc ở

Với $N = 10$, các thương $10, 5, 3, 2, 2, 1, 1, 1, 1, 1$ chia thành năm khối. Trong mỗi khối thương không đổi, nên những tổng như tổng các $d \cdot \lfloor N/d \rfloor$ chỉ còn là tổng cấp số cộng $l + \dots + r$ nhân với thương.

for (ll l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}

Ví dụTổng Các Ước Trên Một Đoạn Đầu

Đề. Cho $N \le 10^{12}$, tính $\sigma(1) + \sigma(2) + \dots + \sigma(N)$ modulo $10^9 + 7$, với $\sigma(x)$ là tổng các ước của $x$.

Lời giải. Đếm theo ước: ước $d$ có mặt trong đúng $\lfloor N/d \rfloor$ số $x \le N$, mỗi lần góp $d$, nên tổng là $1 \cdot \lfloor N/1 \rfloor + 2 \cdot \lfloor N/2 \rfloor + \dots + N \cdot \lfloor N/N \rfloor$. Gộp khối: trong khối $[l, r]$ có thương $q$, phần góp là $q \cdot (l + \dots + r)$. Tổng $l + \dots + r = \frac{(l + r)(r - l + 1)}{2}$; hai thừa số khác tính chẵn lẻ nên chia 2 trên thừa số chẵn trước, rồi mới lấy modulo, tránh tích $10^{24}$ tràn. Khoảng $2 \cdot 10^6$ khối.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
ll n;

ll sum(ll l, ll r) {
    ll a = l + r, b = r - l + 1;
    if (a % 2 == 0) a /= 2;
    else b /= 2;
    return a % MOD * (b % MOD) % MOD;
}

signed main() {
    cin >> n;
    ll ans = 0;
    for (ll l = 1, r; l <= n; l = r + 1) {
        ll q = n / l;
        r = n / q;
        ans = (ans + q % MOD * sum(l, r)) % MOD;
    }
    cout << ans << '\n';
}

ChạyInput10

Output87