×

# PRCN16B - Editorial

Editorialist: Rounaq Jhunjhunu Wala

EASY

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$.

263
accept rate: 25%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×348
×5

question asked: 14 Oct '16, 22:36

question was seen: 1,912 times

last updated: 20 Mar '17, 21:55