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

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()