You are not logged in. Please login at www.codechef.com to post your questions!

×

PRCN16B - Editorial

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

asked 14 Oct '16, 22:36

rounaqwl66's gravatar image

2★rounaqwl66
263
accept rate: 25%

edited 20 Mar '17, 21:55

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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