1212 - Sumă Pătrare

Sursa: [1]

Cerinţa

Fiind dat N, un număr natural nenul, calculați suma S=1^2 + 2^2 + 3^2 + ... + n^2, modulo 10.234.573.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restrictiilor impuse", apoi pe un rând nou va afișa valoarea S. În caz contrar, se va afișa mesajul: "Datele de intrare nu corespund restrictiilor impuse".

Restricţii şi precizări

• 1 ⩽ N ⩽ 2.000.000.000

Exemplul 1

Intrare

Introduceti numarul n: 4

Ieșire

Rezultatul este: 30

Exemplul 2

Intrare

0

Ieșire

n trebuie sa fie intre 1 si 2.000.000.000.

Rezolvare

<syntaxhighlight lang="python" line>

1. 1212

def suma_patrate_modulo(n):

   numarator = (n * (n + 1) % 10234573) * ((2 * n + 1) % 10234573)
   numitor = 6 % 10234573
   invers_modular_numitor = pow(numitor, 10234571, 10234573)
   rezultat = (numarator * invers_modular_numitor) % 10234573
   return rezultat

def validare_n(n):

   if n < 1 or n > 2000000000:
       print("Datele de intrare nu corespund restrictiilor impuse")
       exit()

if __name__ == '__main__':

   n = int(input("Introduceti numarul n: "))
   validare_n(n)
   rezultat = suma_patrate_modulo(n)
   print(f"Datele de intrare corespund restrictiilor impuse\n {rezultat}")

</syntaxhighlight>

Explicatie rezolvare

Acest program calculează suma pătratelor primelor n numere naturale, exprimată modulo 10234573. Programul primește un număr întreg n și verifică dacă acesta se încadrează într-un interval specific. Dacă numărul este valid, programul calculează suma pătratelor folosind formula matematică corespunzătoare și apoi exprimă rezultatul modulo 10234573.

Funcția validare_n(n) primește numărul n și verifică dacă acesta se încadrează în intervalul [1, 2000000000]. Dacă numărul este în afara acestui interval, se afișează un mesaj de eroare și programul se oprește folosind funcția exit().

Funcția suma_patrate_modulo(n) calculează suma pătratelor primelor n numere naturale folosind formula numarator / numitor exprimată modulo 10234573, unde numărătorul și numitorul sunt date de:

numarator = (n * (n + 1) % 10234573) * ((2 * n + 1) % 10234573)

numitor = 6 % 10234573

Pentru a evita erorile de calcul, se calculează inversul modular al numitorului, utilizând funcția pow(). Inversul modular al numărului a este definit ca numărul b, astfel încât a * b % m = 1, unde m este un număr prim.

În secțiunea principală a programului, utilizatorul este întrebat să introducă numărul n. Apoi, se verifică dacă numărul introdus este valid folosind funcția validare_n(n). Dacă numărul este valid, se calculează suma pătratelor folosind funcția suma_patrate_modulo(n) și se afișează pe ecran împreună cu un mesaj de confirmare a validării numărului introdus.