Chia kẹo (Đề tự luyện HSG Tin 12 – Bài 1) – Chia khối theo N/k và số học modulo

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 1 (đề tự soạn) Độ khó: Khá Số học Chia khối ⌊N/k⌋ Số học modulo

Đề bài

Chia kẹo

Thầy Sơn có $N$ viên kẹo. Lần lượt với $k = 1, 2, \dots, M$, thầy chia đều $N$ viên cho $k$ bạn (mỗi bạn nhận như nhau và nhiều nhất có thể), phần dư $N \bmod k$ thầy giữ lại; kẹo được gom lại trước mỗi lần chia. Tính

$$S = \sum_{k=1}^{M} (N \bmod k)$$

và in ra $S$ chia lấy dư cho $10^9 + 7$.

Dữ liệu vào: hai số nguyên $N, M$ $(1 \le N, M \le 10^{12})$.

Subtask:

• Subtask 1 (30%): $N, M \le 10^6$.
• Subtask 2 (40%): $M \le N$.
• Subtask 3 (30%): không có ràng buộc gì thêm.

Input

10 15

Output

63

Giải thích

k = 1..10: 0 0 1 2 0 4 3 2 1 0 → 13
k = 11..15: dư cả 10 viên → 50
Tổng 63

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Chia kẹo

Lời mở đầu

Câu 1 của đề lớp 12 nhìn thì "chỉ là một vòng for", nhưng $M$ tới $10^{12}$ thì vòng for đó chạy tới vài giờ. Chìa khóa là một kĩ thuật rất hay gặp trong số học thi HSG: chia khối theo giá trị của $\lfloor N/k \rfloor$.

Đầu tiên viết lại phần dư bằng phần nguyên:

$$N \bmod k = N - k \cdot \left\lfloor \frac{N}{k} \right\rfloor$$

Điều thú vị là khi $k$ chạy từ $1$ đến $N$, giá trị $\lfloor N/k \rfloor$ chỉ nhận rất ít giá trị khác nhau – không quá $2\sqrt{N}$ giá trị – và các $k$ có cùng giá trị thì đứng liền nhau thành từng khối:

Với $N = 20$: 20 giá trị $k$ nhưng chỉ có 8 khối (8 màu). Với $N = 10^{12}$ chỉ có khoảng $2 \cdot 10^6$ khối.

Cách 1Vét cạn O(M) · 30%Cách 2Chia khối khi M ≤ N · 40%Cách 3Chia khối + phần k > N · 100%

Cách 1Vét cạn từng $k$ – O(M) · 30%

Làm đúng như đề: cộng dồn N % k với mọi $k$ từ $1$ đến $M$, lấy dư sau mỗi bước để khỏi tràn.

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

// Cach 1: vet can tung k - O(M): 30%
int main(){
    long long N, M;
    cin >> N >> M;
    const long long MOD = 1000000007LL;
    long long S = 0;
    for(long long k = 1; k <= M; k++){
        S = (S + N % k) % MOD;
    }
    cout << S;
    return 0;
}

# Cach 1: vet can tung k - O(M): 30%
N, M = map(int, input().split())
MOD = 10**9 + 7
S = 0
for k in range(1, M + 1):
    S += N % k
print(S % MOD)

Không gian$O(1)$

Thời gian$O(M)$

Với $M \le 10^6$ chạy tức thì. Với $M = 10^{12}$ cần $10^{12}$ phép chia – quá thời gian ở cả subtask 2 và 3.

Cách 2Chia khối theo $\lfloor N/k \rfloor$ – O(√N) · 40%

Từ công thức trên:

$$S = M \cdot N - \sum_{k=1}^{M} k \cdot \left\lfloor \frac{N}{k} \right\rfloor$$

Tìm khối chứa $k = l$

Đặt $q = \lfloor N/l \rfloor$. Số $k$ lớn nhất vẫn còn $\lfloor N/k \rfloor = q$ là $r = \lfloor N/q \rfloor$. Trong cả khối $[l, r]$, mọi $k$ có cùng $\lfloor N/k \rfloor = q$, nên phần cần trừ là $q \cdot (l + (l+1) + \dots + r) = q \cdot \dfrac{(l + r)(r - l + 1)}{2}$. Xong khối thì nhảy $l = r + 1$.

Vì sao chỉ có $O(\sqrt{N})$ khối? Với $k \le \sqrt{N}$ có không quá $\sqrt{N}$ giá trị $k$; với $k > \sqrt{N}$ thì $\lfloor N/k \rfloor < \sqrt{N}$ nên cũng chỉ có không quá $\sqrt{N}$ giá trị. Các bạn kéo thử ở khung dưới để thấy các khối ghép lại thế nào:

N M

Ví dụ nhanh:

Code này chỉ đúng khi $M \le N$:

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

// Cach 2: N mod k = N - k*(N/k), gom cac k co cung N/k thanh mot khoi - O(sqrt N)
// (chi dung khi M <= N): 40%
const ll MOD = 1000000007LL, INV2 = 500000004LL;   // INV2 = nghich dao cua 2 theo MOD
int main(){
    ll N, M;
    cin >> N >> M;
    ll S = (M % MOD) * (N % MOD) % MOD;          // tong cua N, M lan
    for(ll l = 1, r; l <= M; l = r + 1){
        ll q = N / l;                            // moi k trong [l, r] deu co N/k = q
        r = min(M, N / q);
        ll sumk = ((l + r) % MOD) * ((r - l + 1) % MOD) % MOD * INV2 % MOD;   // l + (l+1) + ... + r
        S = (S - (q % MOD) * sumk % MOD + MOD) % MOD;
    }
    cout << S;
    return 0;
}

# Cach 2: gom khoi cac k co cung N // k - O(sqrt N), chi dung khi M <= N: 40%
N, M = map(int, input().split())
MOD = 10**9 + 7
S = M * N
l = 1
while l <= M:
    q = N // l
    r = min(M, N // q)
    S -= q * (l + r) * (r - l + 1) // 2     # Python khong tran so
    l = r + 1
print(S % MOD)

Vì sao cách 2 sai khi M > N?

Khi $l > N$ thì $q = \lfloor N/l \rfloor = 0$ và phép N / q là chia cho 0 – chương trình chết ngay. Subtask 1 có test $M > N$ nên cách 2 không ăn được cả subtask 1, chỉ được 40% của subtask 2.

Cách 3Chia khối cho $k \le \min(N, M)$, phần còn lại tính một lần – O(√N) · 100%

Với $k > N$ thì không chia được viên nào cho mỗi bạn, nên $N \bmod k = N$. Cả đoạn $k = N + 1, \dots, M$ góp đúng $(M - N) \cdot N$. Vậy chỉ chia khối trên $k = 1..L$ với $L = \min(N, M)$, rồi cộng thêm phần đó nếu $M > N$.

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

// Cach 3: chia khoi cho k <= min(N, M), con k > N thi du luon bang N - O(sqrt N): 100%
const ll MOD = 1000000007LL, INV2 = 500000004LL;
int main(){
    ll N, M;
    cin >> N >> M;
    ll L = min(N, M);
    ll S = (L % MOD) * (N % MOD) % MOD;
    for(ll l = 1, r; l <= L; l = r + 1){
        ll q = N / l;
        r = min(L, N / q);
        ll sumk = ((l + r) % MOD) * ((r - l + 1) % MOD) % MOD * INV2 % MOD;
        S = (S - (q % MOD) * sumk % MOD + MOD) % MOD;
    }
    if(M > N) S = (S + ((M - N) % MOD) * (N % MOD)) % MOD;   // k = N+1 .. M: moi lan du N
    cout << S;
    return 0;
}

# Cach 3: chia khoi cho k <= min(N, M), con k > N thi du bang N - O(sqrt N): 100%
N, M = map(int, input().split())
MOD = 10**9 + 7
L = min(N, M)
S = L * N
l = 1
while l <= L:
    q = N // l
    r = min(L, N // q)
    S -= q * (l + r) * (r - l + 1) // 2
    l = r + 1
if M > N:
    S += (M - N) * N
print(S % MOD)

Các bạn bấm chạy tay code C++ để xem từng dòng nhé:

C++▶ Chạy tay từng dòng codeCách 3: chia khối theo N/k cho k ≤ L, cộng (M − N)·N nếu M > N.

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

Dữ liệu mẫu:

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

2using namespace std;

3typedef long long ll;

4

5// Cach 3: chia khoi cho k <= min(N, M), con k > N thi du luon bang N - O(sqrt N): 100%

6const ll MOD = 1000000007LL, INV2 = 500000004LL;

7int main(){

8 ll N, M;

9 cin >> N >> M;

10 ll L = min(N, M);

11 ll S = (L % MOD) * (N % MOD) % MOD;

12 for(ll l = 1, r; l <= L; l = r + 1){

13 ll q = N / l;

14 r = min(L, N / q);

15 ll sumk = ((l + r) % MOD) * ((r - l + 1) % MOD) % MOD * INV2 % MOD;

16 S = (S - (q % MOD) * sumk % MOD + MOD) % MOD;

17 }

18 if(M > N) S = (S + ((M - N) % MOD) * (N % MOD)) % MOD; // k = N+1 .. M: moi lan du N

19 cout << S;

20 return 0;

21}

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

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

Bẫy tràn số khi lấy dư

Với $l, r$ cỡ $10^{12}$, tích $(l + r)(r - l + 1)$ có thể tới $10^{24}$ – vượt xa long long ($9.2 \cdot 10^{18}$). Phải lấy dư từng thừa số trước khi nhân, và thay phép chia 2 bằng nhân với nghịch đảo của 2 theo modulo: $2^{-1} \equiv 500000004 \pmod{10^9+7}$. Tương tự, $q \cdot \text{sumk}$ cũng phải lấy dư $q$ trước. Phép trừ thì cộng thêm MOD để không ra số âm.

Bộ test chấm "bắt" những lỗi nào?

Cách làm	Sub 1	Sub 2	Sub 3	Điểm
Cách 1 – vét cạn O(M)	Đúng	TLE	TLE	30
Cách 2 – quên phần k > N	Sai	Đúng	Sai	40
Cách 3 nhưng tính (l+r)*(r-l+1)/2 rồi mới lấy dư	Đúng	Sai	Sai	30
Cách 3 đầy đủ	Đúng	Đúng	Đúng	100

Ghi chú của mình: các code C++ đã được nộp thử trên ClueOJ với đúng bộ test của bài. Bản Python cách 3 cho kết quả đúng (Python không tràn số nên khỏi lo phần nghịch đảo), nhưng với $N = 10^{12}$ có test chạy khoảng 1–2 giây.

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 😇