Corjuc Eunice: Pagină nouă: 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 l...

2024-01-04T16:49:30Z

Pagină nouă: Se dau <code>N</code> numere naturale <code>a[1], a[2], ..., a[N]</code> şi un număr natural nenul <code>M</code>. = Cerința = Să se determine numărul perechilor de indici <code>(i, j)</code>, cu <code>i < j</code>, cu proprietatea că numărul <code>a[i]*a[j]+a[i]+a[j]</code> este divizibil cu <code>M</code>. = Date de intrare = Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>N</code> şi <code>M</code>, iar pe următoarea l...

New page

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

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

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>N</code> şi <code>M</code>, iar pe următoarea linie cele <code>N</code> numere naturale <code>a[1], a[2], ..., a[N]</code>, separate prin spaţiu.

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

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>
* <code>0 ≤ a[i] ≤ 1018</code>, pentru orice <code>i∈{1, 2, ..., N}</code>
* <code>1 ≤ M ≤ 1017</code>

== Exemplul 1 ==
input.txt:

4 13

6 15 6 1

output.txt:

2

Explicație:

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

== 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>

3775 - Prosum - Revision history