trang chủ / đề bài / icpc21_nat_l

Cặp số may mắn

Đề bài

Mô tả

Một cặp số nguyên dương (x,y) được gọi là cặp may mắn khi và chỉ khi tồn tại số nguyên dương k sao cho xk+yk chia hết cho x·y. Ví dụ:

  • (2,4) là cặp may mắn vì 23+43=8+64=72 chia hết cho 2·4=8;
  • (3,3) là cặp may mắn vì 32+32=9+9=18 chia hết cho 3·3=9;
  • (1,2) không phải cặp may mắn vì 1k+2k luôn lẻ với mọi k>0 nên không thể chia hết cho 1·2=2.

Cho mảng a gồm n số nguyên dương, hãy đếm số cặp chỉ số (i,j) sao cho i<j và (ai,aj) là cặp may mắn.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n, độ dài của mảng.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an, các phần tử của mảng.

Dữ liệu ra

In ra một số nguyên là số cặp may mắn trong mảng a.

Ràng buộc

  • 2≤n≤3·105.
  • 1≤ai≤107.

Ví dụ

Input Output Giải thích
6
1 2 3 4 5 6
1 Chỉ có cặp (2,4) là cặp may mắn.
4
7 7 7 7
6 Mọi cặp (7,7) đều là cặp may mắn, có 6 cặp chỉ số.

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