1124 - Patrate

Cerința

Dându-se n, un număr natural, să se afle numărul de pătrate care au colţurile coordonate numere întregi cuprinse între 0 şi n inclusiv.

Date de intrare

Programul citește de la tastatură un număr natural n.

Date de ieșire

Programul va afişa pe ecran un număr natural, reprezentând numărul de pătrate formate cu cele (n+1)2 puncte. Deoarece rezultatul poate fi mare, se va afişa răspunsul modulo 666013.

Restricții și precizări

• 1 ⩽ n ⩽ 2.000.000.000
• Pentru teste în valoare de 30 de puncte, n ≤ 10
• Pentru teste în valoare de 75 de puncte, n ≤ 2.000.000

Exemplu

Intrare

2

Ieșire

6

Explicație

Pătratele ce se formează au colţurile:

1. (0, 0), (0, 1), (1, 1), (1, 0)
2. (0, 1), (0, 2), (1, 2), (1, 1)
3. (1, 0), (1, 1), (2, 1), (2, 0)
4. (1, 1), (1, 2), (2, 2), (2, 1)
5. (0, 0), (0, 2), (2, 2), (2, 0)
6. (0, 1), (1, 2), (2, 1), (1, 0)

Rezolvare

<syntaxhighlight lang="python"> def validate_input(n):

   if n < 1 or n > 2000000000:
       raise ValueError("n trebuie sa fie intre 1 si 2.000.000.000")

def calculate_sum(n):

   validate_input(n)
   sol = 0
   mod = 666013

   n %= mod

   for i in range(n):
       sol += (n - i) * (n - i) * (i + 1)
       sol %= mod

   return sol

def main():

   n = int(input())
   sol = calculate_sum(n)
   print(sol)

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicație cod

Acest cod definește trei funcții și o funcție principală:

Funcția validate_input(n) verifică dacă valoarea parametrului n este cuprinsă între 1 și 2.000.000.000, și aruncă o excepție ValueError dacă nu este.

Funcția calculate_sum(n) primește un parametru n și calculează suma unei anumite formule matematice, bazată pe valoarea lui n și un număr constant (mod = 666013). Apoi, funcția returnează această sumă.

Funcția main() citește un număr întreg de la tastatură, apelează funcția calculate_sum(n) pentru a calcula suma corespunzătoare, și apoi afișează rezultatul.

Dacă acest script este rulat ca un program, atunci funcția main() este apelată.