201
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:
(0, 0), (0, 1), (1, 1), (1, 0)
(0, 1), (0, 2), (1, 2), (1, 1)
(1, 0), (1, 1), (2, 1), (2, 0)
(1, 1), (1, 2), (2, 2), (2, 1)
(0, 0), (0, 2), (2, 2), (2, 0)
(0, 1), (1, 2), (2, 1), (1, 0)
#include <bits/stdc++.h> #define mod 666013 using namespace std; long long n , n1 , n2; int main() { cin >> n; n1 = (n + 1) * (n + 1); n2 = n1 - 1; if(n1 % 4 == 0) n1 /= 4; else n2 /= 4; if(n1 % 3 == 0) n1 /= 3; else n2 /= 3; cout<<((n1 % mod) * (n2 % mod)) % mod; return 0; }
Comentarii