Hướng dẫn cho Tổng tích


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

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: cuom1999

Sub 1:

Nhận thấy rằng \(a_i + a_j\)\(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)\)\((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\)\(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


  • -4
    20NguyenLeMinh    11:14 a.m. 15 Tháng 5, 2021

    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

      \(0 \leq a_i \leq 10 ^ 4\)\(p = 10 ^ 9\) thì \(2 \times max(a_i) = 2 \times 10 ^ 4 < 10 ^ 9\)\(max(a_i) ^ 2 = 10 ^ 8 < 10 ^ 9\) rồi :v


      • -4
        20NguyenLeMinh    9:52 p.m. 15 Tháng 5, 2021

        he sorry a , em quên sub1 p = 1e9 :vv

      1 bình luận nữa