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

×

can someone provide me solution of Suhana and Equation?

0
1

please explain your approach? is there is any formulae?

asked 27 Jul '17, 22:06

vivek96's gravatar image

2★vivek96
533221
accept rate: 8%


10

This problem was from a very old contest, you can see all sorts of solutions here.

In fact, a lot of people copied the same solutions from that contest...

Here's mine, which takes $O(M\times log(N))$ in runtime.

My thought process went like this:

First, realize that $x^p \equiv (x \bmod M)^p \bmod M$.

This reduces $\displaystyle\sum_{c=0}^{N} c^c \bmod M$ for all $c > M$ to a geometric series sum where $c < M$, essentially:

$\displaystyle\sum_{c=0}^{N} c^c \bmod M \equiv \displaystyle\sum_{c=0}^{M-1} \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{c + k M} \bmod M$,

Which can be broken down into: $\displaystyle\sum_{c=0}^{M-1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M$,

As fast as that sounds, all that left right now is to calculate the geometric series sum $\displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{kM} \bmod M$, which can be reduced to the geometric series formula. However, because $M$ is not always coprime with the divisor, I cannot use the formula with Modular Multiplicative Inverse and Fermat's little theorem. I can, however, use matrix exponentiation to calculate the sum:

$\begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix} ^ {\lfloor\frac{N-c}{M}\rfloor} = \begin{pmatrix}c^{M {\lfloor\frac{N-c}{M}\rfloor}} & \displaystyle\sum_{k=0}^{{\lfloor\frac{N-c}{M}\rfloor} - 1} c^{kM} \bmod M \\ 0 & 1 \end{pmatrix}$

Adding the 2 components on the first row gives the geometric series sum. This means I can apply fast exponentiation to the matrix exponentiation and that will calculate the sum in $O(log(\lfloor\frac{N-c}{M}\rfloor))$ time.

In total, I took $M-1$ iterations of $O(log(M) + log(\lfloor\frac{N-c}{M}\rfloor))$ to calculate $c^c$ and geometric series sum. And reducing the runtime estimation:

$O(log(M) + log(\lfloor\frac{N-c}{M}\rfloor)) = O(log(M) + log(N) - log(M)) = O(log(N))$,

Thus my runtime ended at $O(M\times log(N))$ and I am done.

Quick note that for $c = 0$ only $0^0 = 1$, and all other $0^k = 0$, thus our actual answer will be:

$\displaystyle\sum_{c=0}^{N} c^c \bmod M \equiv 1 + \displaystyle\sum_{c=1}^{M-1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M$.

For a detailed explanation, read below.

View Content
link

answered 27 Jul '17, 23:09

liaojh's gravatar image

5★liaojh
1825
accept rate: 7%

edited 29 Jul '17, 05:27

the solution provided by 5 star guy @Mr is not the way an actual 2 or 3 star person can understand..its actually a high level..it shud hve broken down in steps in order to understand..just because u understand it doesn"t mean u can put it in same way to different person...basically less than 5 star people needs more explanation to understand the logics..try to provide better explanation dude..no hard feelings...cheers up!

link

answered 29 Jul '17, 01:11

ruhul1995's gravatar image

1★ruhul1995
6717
accept rate: 6%

edited 29 Jul '17, 01:12

1

@liaojh uses standard mathematical notation and his approach is pretty clear. He has even provided a link to a tutorial for matrix exponentiation, which is the core algorithm he has used. Maybe you should actually put in some effort into understanding the solution.

(29 Jul '17, 01:43) meooow ♦6★
1

@ruhul1995 updated for you, if you wanna read it

(29 Jul '17, 05:27) liaojh5★
-1

if(m<=n) e.g : (2^2+(m+2)^(m+2)+(m2+2)^(m2+2)+.....)mod(m)=2^2(1+2^m+2^2*m+....) which is a simple sum of GP.Do this for m number therfore O(m). else calculate trivialy 1^1+2^2+3^3+... therefore in worst case O(10^3)

You probably know that one can calculate the power of a number in logarithmic time. You can also do so for calculating the sum of the geometric series. Since it holds that1 + a + a^2 + ... + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + ... + (a^2)^n), you can recursively calculate the geometric series on the right hand to get the result.

This way you do not need division, so you can take the remainder of the sum (and of intermediate results) modulo any number you want. algo:- geometricSeriesMod[a_, n_, m_] := Module[ {q = a, exp = n, factor = 1, sum = 0, temp}, While[And[exp > 0, q != 0], If[EvenQ[exp], temp = Mod[factorPowerMod[q, exp, m], m]; sum = Mod[sum + temp, m]; exp--]; factor = Mod[Mod[1 + q, m]factor, m]; q = Mod[q*q, m]; exp = Floor[ exp /2]; ];

Return [Mod[sum + factor, m]] ] Parameters:

a is the "ratio" of the series. It can be any integer (including zero and negative values). n is the highest exponent of the series. Allowed are integers >= 0. m is the integer modulus != 0

my code:-https://www.codechef.com/viewsolution/14665023

link

answered 28 Jul '17, 01:23

pl425's gravatar image

3★pl425
221
accept rate: 50%

3

When copying an explanation from elsewhere you should at least give credit to the original writer. (Source)

(29 Jul '17, 01:58) meooow ♦6★

please explain in easy way for 2-3 star users.huh

(31 Jul '17, 09:09) vivek962★
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:

×3,820
×2,738
×9

question asked: 27 Jul '17, 22:06

question was seen: 853 times

last updated: 31 Jul '17, 09:09