PRCN16B - Editorial

easy
editorial
modulo
proc1601

#1

PROBLEM LINK:

Practice
Contest

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.