PROBLEM LINK:
Editorialist: Rounaq Jhunjhunu Wala
DIFFICULTY:
EASY
PREREQUISITES:
Modulo
PROBLEM:
Given a number N, we need to find the sum of all integers i from 1 to N such that 2^i+1 is divisible by 3.
EXPLANATION:
We can try the naive approach of finding 2^i+1 for 1 \leq i \leq N, and check for 3-divisibility. To handle large exponents, we can take mod at every stage of exponentiation so that the resulting number is small. Finally we can use fast exponentiation to find the powers of 2. But, we can easily see that all the above approaches are \Omega(N) and hence won’t work on the original constraints.
We would need a formula for solving this problem, which we will derive now. We know that 2^i+1 \equiv 0 \mod 3, which is equivalent to 2^i = 2 \mod 3. Now, 2 \equiv 2 \mod 3 and 2^2 \equiv 1 \mod 3, and by the property (a*b)%m = ((a%m)*(b%m))%m, we can deduce that 2^i \equiv 2 \mod 3 if i is odd, else 2^i \equiv 1 \mod 3.
THe above reduces the problem to just finding the sum of odd integers from 1 to N, which can be easily proved to be equal to \lfloor \frac{N+1}{2} \rfloor ^ 2.