Project Euler #28: Number spiral diagonals (C++)

Question

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

Answer : 669171001

Hacker Rank Problem

Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <iostream> unsigned int powmod(unsigned long long base, unsigned int exponent, unsigned int modulo) { unsigned long long result = 1; while(exponent > 0) { if(exponent % 2) { result = (result * base) % modulo; exponent--; } else { base = (base * base) % modulo; exponent /= 2; } } return result; } unsigned int inverseModulo(unsigned a, unsigned int modulo) { return powmod(a, modulo - 2, modulo); } int main() { unsigned int T; std::cin >> T; while(T--) { unsigned long long N; std::cin >> N; unsigned long long x = N / 2; const unsigned int Modulo = 1000000007; x %= Modulo; unsigned long long sharedTerm = (2 * x * (x + 1)) % Modulo; unsigned long long sum1 = ((4 * sharedTerm * (2 * x + 1)) % Modulo) * inverseModulo(3, Modulo); unsigned long long sum2 = sharedTerm + 4 * x + 1; unsigned long long sum = (sum1 % Modulo + sum2 % Modulo) % Modulo; std::cout << sum << std::endl; } return 0; }