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\) 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


  • -14
    NguyenHuuNhatQuang    8:38 p.m. 16 Tháng 4, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • 2
      ZuMinh    2:05 p.m. 17 Tháng 4, 2021

      không cần đâu em :))


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

        mang cnt dem phan phoi thi do i di con gi nua

      1 bình luận nữa