3775 - Prosum

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 input.txt 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 output.txt 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

Exemplul 1

input.txt:

4 13

6 15 6 1

output.txt:

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.

Exemplul 2

input.txt:

99999999999999 13

6 15 6 1

Output:

Invalid input. Please check the constraints.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def is_valid_input(N, M, numbers):

   if not (2 <= N <= 100000):
       return False
   if not (1 <= M <= 10**17):
       return False
   if not all(0 <= a_i <= 10**18 for a_i in numbers):
       return False
   return True

def count_pairs_with_property(N, M, numbers):

   count = 0
   for i in range(N):
       for j in range(i + 1, N):
           if (numbers[i] * numbers[j] + numbers[i] + numbers[j]) % M == 0:
               count += 1
   return count

def main():

   with open("input.txt", "r") as fin:
       N, M = map(int, fin.readline().split())
       numbers = list(map(int, fin.readline().split()))

   if not is_valid_input(N, M, numbers):
       print("Invalid input. Please check the constraints.")
       return

   result = count_pairs_with_property(N, M, numbers)

   with open("output.txt", "w") as fout:
       fout.write(str(result) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>