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