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 3divisibility. 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. asked 14 Oct '16, 22:36
