Rezolvare PBinfo #3775

Se dau N numere naturale a[1], a[2], ..., a[N] şi un număr natural nenul M.

Cerința

Să se determine numărul perechilor de indici (i, j), cu i < j, cu proprietatea că numărul a[i]*a[j]+a[i]+a[j] este divizibil cu M.

Date de intrare

Fișierul de intrare prosum.in conține pe prima linie numerele naturale N şi M, iar pe următoarea linie cele N numere naturale a[1], a[2], ..., a[N], separate prin spaţiu.

Date de ieșire

Fișierul de ieșire prosum.out va conține pe prima linie numărul perechilor de indici (i, j), cu i < j, cu proprietatea că numărul a[i]*a[j]+a[i]+a[j] este divizibil cu M.

Restricții și precizări

• 2 ≤ N ≤ 100.000
• 0 ≤ a[i] ≤ 1018, pentru orice i∈{1, 2, ..., N}
• 1 ≤ M ≤ 1017

Exemplu:

prosum.in

4 13
6 15 6 1

prosum.out

2

Explicație

Există două perechi de indici având proprietatea cerută, (1,4) şi (3,4), deoarece avem 6*1+6+1=13, care este divizibil cu M=13.