Hướng dẫn cho Tổng tích
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Sub 1:
Nhận thấy rằng \(a_i + a_j\) và \(a_ia_j\) luôn bé hơn \(p\). Vì thế ta phải có \(a_i + a_j = a_ia_j\). Phương trình này có nhiều cách giải. Một trong số đó là quy về \((a_i-1)(a_j-1)=1\). Tức là \(a_i - 1 = a_j - 1 = 1\) hoặc \(-1\). Hay \((a_i, a_j)=(0, 0), (2, 2)\). Từ đây đáp số là số cặp \((0, 0)\) và \((2, 2)\) trong dãy.
Sub 2:
Đầu tiên, ta tạo mảng \(cnt[i]\) là số lượng phần tử chia \(p\) dư \(i\). Thay vì dùng 2 vòng lặp cho dãy \(a\), ta sẽ dùng 2 vòng lặp cho các số dư có thể (từ \(0\) đến \(p - 1\)).
for i = 0 .. p - 1
for j = i .. p - 1
if (i + j) % p == i * j % p
đếm số cặp thỏa mãn dựa trên cnt[i] và cnt[j]
Sub 3, 4
Ta dùng ý tưởng của sub 1. Quy về \((a_i - 1)(a_j - 1) \% p = 1\). Nếu đặt \(b_i = (a_i - 1) \% p\), thì \(b_ib_j \% p = 1\). Tức là \(b_j\) là nghịch đảo mod \(p\) của \(b_i\). Đáp số có thể được tính như sau:
for i = 1 .. n
res += cnt[inv(b[i])]
cnt[b[i]]++
Trong đó \(inv(x)\) là nghịch đảo mod p của x. Lưu ý rằng số này chỉ tồn tại nếu \(gcd(x, p) = 1\). Để tính nghịch đảo mod \(p\), ta có thể sử dụng:
- Định lý Fermat nhỏ cho số nguyên tố (sub 3). Tức là \(inv(x) = x^{p-2} \% p\) nếu \(p\) là SNT.
- Định lý Euler (sub 4). Tức là \(inv(x) = x^{phi-1} \% p\) với \(phi\) là phi hàm Euler của \(p\).
- Thuật toán Euclid mở rộng (sub 4). Tức là tìm \(a,b\) sao cho \(ax + bp = 1\). Khi đó \(inv(x) = a \% p\).
Bình luận
sao lai nhan thay rang ai + aj ,ai*aj luon be hon p ?
2 + 2 = 2 * 2 dong du 1 mod 3
-
1
kitsune
9:00 p.m. 15 Tháng 5, 2021
-
-4
20NguyenLeMinh
9:52 p.m. 15 Tháng 5, 2021
1 bình luận nữa\(0 \leq a_i \leq 10 ^ 4\) và \(p = 10 ^ 9\) thì \(2 \times max(a_i) = 2 \times 10 ^ 4 < 10 ^ 9\) và \(max(a_i) ^ 2 = 10 ^ 8 < 10 ^ 9\) rồi :v
he sorry a , em quên sub1 p = 1e9 :vv