trang chủ / đề bài / countpairs

Đếm cặp

Đề bài

Mô tả

Cho số nguyên tố p, n số nguyên đôi một khác nhau a1,a2,…,an và số nguyên k.

Hãy đếm số cặp chỉ số (i,j) với 1≤i<j≤n sao cho

(ai+aj)(ai2+aj2)≡k(modp).

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, p, k.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an.

Dữ liệu ra

In ra một số nguyên duy nhất là số cặp thỏa mãn.

Ràng buộc

  • 2≤n≤3·105
  • 2≤p≤109, p là số nguyên tố
  • 0≤k≤p−1
  • 0≤ai≤p−1, các ai đôi một khác nhau

Ví dụ

Input Output Giải thích
3 3 0
0 1 2
1 (0+1)(02+12)=1≡1, (0+2)(02+22)=8≡2, (1+2)(12+22)=15≡0(mod3). Chỉ cặp (2,3) thỏa mãn.
6 7 2
1 2 3 4 5 6
3 Có 3 cặp thỏa mãn: (1,5), (2,3), (4,6).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0