Chocolate Chips,

We’ve been hard at work developing a new and improved CodeChef 2.0 site. Here’s a short list of features you can expect in the coming weeks: shoutbox/chat, campus dashboards, a help wiki, rankings page, individual statistics, levels, awards and more…

Take a look:

This is not a final mockup but hints at some of the new features we are rolling out. You’ll start seeing updates in the next few weeks. Enjoy!

Cheers,

Chef

CodeChef MPSTME and ACM MPSTME have come together to present “The Open Book Programming Competition“.

As the name suggests, the contestants are allowed to bring books and material related to the languages or the compilers used. The contest is hosted on CodeChef as a part of the CodeChef Campus Chapter Program. This is a closed competition and the contest URL shall be revealed to students present at the venue. So if you are a college student in Mumbai and would like to participate make sure to register and reach the venue on time.

**Details of the competition:**

**Date:** 1st September, 2009

**Timing**: 4 pm – 6 pm

**Venue:** Mukesh Patel School of Technology Management and Engineering, NMIMS University, Mumbai.

**Registrations: **Online Registrations are open at www.theobpc.co.cc . There are limited number of seats and the registrations will be closed as soon as the seats are filled.

**The Prizes for the Competition are:**

- 1st Prize: Philips DVD Player sponsored by Croma, CodeChef TShirt
- 2nd Prize: Rs.750 Cash, CodeChef TShirt
- 3rd Prize: Rs.500 Cash, CodeChef TShirt

Consolation Prizes to be given as well.

CodeChef MPSTME Chapter is also organizing a session for MPSTME students where Vikram Ghotgalkar, Software Developer, Directi (~vix on CodeChef twitter) will demonstrate a basic implementation of a Search Engine in 30 mins. This will be followed by a prize distribution round of “The Open Book Programming Competition”.

For further details please visit www.theobpc.co.cc or mail in to acm.mpstme@gmail.com

If you’d like to host your contest on CodeChef, feel free to mail us at contests@codechef.com

Cheers!

Anusha

Once again, it’s time we announce the CodeChef Programmer of the Month. The guy’s been topping most contests and if you’re wondering why he didn’t win the August Mini Challenge, it was because he set the problem! Everyone wants to know about the person behind the username syco and profiling him has been long overdue.

Without beating around the bush any further, let me introduce you to our Programmer for September ’09, Varun Jalan!

**Name:** Varun Jalan

**Age:** 21

**Institute:** Columbia University

**UserID:** syco

**1. How/When did you start programming?**

I learnt Q Basic around 8 years back. However, I’ve known C for only about 5 years. I started learning algorithms around two and a half years back. My brother taught me C (though I was very, very reluctant to learn that time )

**2. What do you do when you’re not programming?**

Mostly surfing the net and reading books.

**3. What do you like most about CodeChef?
**The prizes definitely . A couple of problems in each contest are really good, though in my opinion they are too tough to be a part of any contest of duration <= 5 hours.

**4. How many hours a day do you program?**

That varies greatly. Can range from 0 – 15 hours a day.

**5. What’s your favourite book and why?**

I read books like the Harry Potter series, Lord of the Rings etc. Amongst algorithms and programming stuff, I like The C programming language(Kernighan and Ritche), CLRS.

**6. If you could eat dinner with any famous person (past or present), who would it be and what dish would you have?**

Never given it a thought Perhaps share a pizza with Einstein ? lol

**7. What are your plans for the future?**

I ll be completing my MS at Columbia Univ. by next December. I’ll mostly be working after that, though I still am considering PhD as an option.

Greetings everyone!

We are happy to introduce a rating system for Codechef based on the contests we have every month. In brief, the rating system will have the following features.

1. Every user will have a rating. The user with the highest rating will be ranked 1, the user with the next highest rating will be ranked 2 and so on.

2. The ratings for the users will depend only on how they perform in the contests and not how they perform in the practice section.

3. Every contest problem will get a particular value based on the number of users solving that problem. The maximum value for a problem tends to the value 5 and the minimum value for a problem tends to 1. So, every user is guaranteed at-least 1 point for solving a problem. The selection of the value 5 was to give sufficient room for the top performers to increase their rating. Selection of a smaller range of values would let those participants solving only easy problems and participating frequently overtake those not participating frequently but performing exceptionally well when they do. Suppose the total number of users who have solved a particular problem is PS and the total number of users who have participated in the contest is TS, then the point value for a particular problem is 5 – 4*PS/TS. So, if there are more users successfully solving a problem, it’s value will be less and vice versa. The Challenge problem point value is calculated by taking the product of the score for the challenge problem with the maximum rating a contest problem can have i.e 5.

4. Suppose a user has solved P binary problems and 1 challenge problem and at the end of the contest, these problems have the values V1, V2, .. ,Vp then the total rating score S of the user for that contest will be V1+V2+…+Vp + 5 * (score of the user for the challenge problem).

5. The new rating of the user will be old_rating+S.

Also, every user’s profile page will now have a rating graph along with the current rating and rank. Your feedback in this regard is much appreciated

Regards,

Aniruddha.

Here is a nice tutorial for the problem Quadratic Equations, courtesy Neelesh Bodas

This tutorial discusses one of the “hard problems” of the July Contest – Quadratic Equations. I called this problem “hard” because it is placed in the “hard problems” category and there were only 5.25% successful submissions for this problem. However, I believe this was actually one of the easy problems in this competition – provided you knew a little bit of number theory. Let’s see how.

To begin with, let’s get rid of all the verbosity from the problem statement and understand what the problem actually asks. In simplest terms, the problem asks us to find all possible values of w such that (Aw^{ 2 } +Bw+C) is divisible by prime P. In mathematical terms, the task is to find all possible solutions for the congruence:

Aw^{2}+Bw+C ≡ 0 (mod P)

———– [A]

With Constraints: 0 < A < P, 0 ≤ w, B, C < P < 10^{6}.

Incidentally, if you are a number theory fan, chances are that you already know the answer to this problem. Typically this scenario would be discussed in almost every number theory book, and is usually covered under the heading quadratic residues

Before we go into the detailed solution, let’s jot down few basic points first –

- Can a brute-force solution work? (In almost all programming problems, it becomes very important to understand whether or not the brute-force solution would work without actually writing the code and testing it out. Of course in most of the problems it wouldn’t work.). In the current case, since there are about 10000 test cases and each test case would need 10
^{6}iterations in the worst case, the total number of iterations would be 10^{10}. Convince yourself that an empty loop that runs 10^{10}times needs much more time than 3 seconds. The brute-force approach thus gets ruled out. - Observe that since w < P, smaller cases with lower values of P are very easy to handle. For example, when P=2, the only values that w may take are 0 and 1. Similarly when P=3, the only allowed values for w are 0,1 and 2. Thus we can use the brute-force approach for smaller values of P, like 2, 3,5 etc.
- Since B and C can be zero, it makes sense to deal with these cases separately, as the problem could reduce to a less-complicated version in these cases. Observe that:
- If B=C=0, then the problem reduces to finding all w such that P | (Aw
^{2}).Since 0 < A < P and 0 ≤ w < P, the only solution is w = 0. - If C=0 but B≠0, then the problem reduces to finding all w such that w*(Aw+B) ≡ 0 (mod P). Since P is prime, this implies that P|w or P|(Aw+B). Clearly, w = 0 is one solution, and other solutions would be obtained by solving the linear congruence
Aw+B ≡ 0 (mod P)———– [B]
Thus observe that in this case we have reduced the problem of solving a quadratic congruence to solving a linear congruence.

- If B=0 but C≠0 then the problem reduces to finding all w such that
Aw
^{2}+C ≡ 0 (mod P)———– [C]Again observe that we have a special case of quadratic congruence here, which doesn’t have any linear term.

- If B=C=0, then the problem reduces to finding all w such that P | (Aw
- In fact, the original congruence in [A] can always be reduced to a form similar to [C] even in the most general case, when 0 < A,B,C < P. The trick is to do the “square completion”. Observe that we can rewrite [A] as:
A
^{2}w^{2}+4ABw+4AC+B^{2}-B^{2}≡ 0 (mod P)⇔ (2Aw+B)

^{2}+(4AC-B^{2}) ≡ 0 (mod P)Let u=2Aw+B and D=(4AC-B

^{2}). Then the congruence can be rewritten as:u

^{2}+ D ≡ 0 (mod P)Of course, if u or D are not between 0 to P-1, then can be changed modulo P to bring them in the required range.

Thus, the most general case of [A] needs a two-step solution:

- Solve the following quadratic congruence for u:
u
^{2}+(4AC-B^{2}) ≡ 0 (mod P)———– [D] - Solve the following linear congruence for w:
(2Aw+B) ≡ u (mod P)i.e. 2Aw ≡ (u-B) (mod P)———– [E]
where u is the solution obtained in step (1).

- Solve the following quadratic congruence for u:

Thus it should be clear by now that this entire problem is all about dealing with linear and quadratic congruences. Incidentally, a quick google search provides us with all references that are necessary (and sufficient) to solve this problem. That’s why I referred this problem as an “easy problem” in the beginning.

In the remainder of this tutorial we shall see how to solve linear and quadratic congruences. The task of putting these two concepts together and solving the actual problem is (purposely) left as an exercise to the reader.

**Task**: Find all possible solutions to the congruence

Mw ≡ N (mod P)

**Constraints**: P is prime, 0 < M,N,w < P

Let’s take a simple example to understand this case. Let M = 4, N = 3 and P = 11. The following table lists the required values-

w mod P | (Mw) mod P | (Mw – N) mod P |

0 | 0 | 8 |

1 | 4 | 1 |

2 | 8 | 5 |

3 | 1 | 9 |

4 | 5 | 2 |

5 | 9 | 6 |

6 | 2 | 10 |

7 | 6 | 3 |

8 | 10 | 7 |

9 | 3 | 0 |

10 | 7 | 4 |

The first column lists all possible values of “w mod P” and the other two columns represent the corresponding values for “(Mw) mod P” and “(Mw-N) mod P” respectively. Observe that no values seem to be repeated in second or third column. In other words, it looks like all values of “(Mw) mod P” are different when w belongs to the set {0,1,…,P-1}.

It is easy to see that this observation will always hold. To see why, suppose there are two distinct values of w, say w1 and w2, with 0 ≤ w2 < w1 < P, such that

Mw1 ≡ k (mod P) and

Mw2 ≡ k (mod P)

for some k. This would imply that Mw1 ≡ Mw2(mod P), which means P | M(w1-w2), which in turn means P | (w1-w2) : a contradiction since P > w1 > w2 ≥ 0.

Thus we see that every entry in column-2 will be different (and each entry will be between 0 to P-1 inclusive). As there are exactly P entries in column 2, this means that every entry in the set {0,1,…,(p-1)} will occur *exactly once* in column-2. Consequently, there would be exactly one value of w which would evaluate to N in column-2. In fact, this is the value of w that we are looking for, since this is the only value that satisfies Mw ≡ N (mod P). (Applying this argument to the example above, we would return w = 9 as our answer to the congruence Mw ≡ N (mod P)).

Moral of the story – The linear congruence Mw ≡ (mod P) with 0<M,N<P has exactly **one** solution. And the good news is that it is not at all difficult to find what this solution would be.

Let w = k represent this solution. Then we have:

Mk ≡ N (mod P)

i.e. (Mk – N = Pu) for some integer u.

Rearranging the terms, we get Mk + P(-u) = N.

Observe that since GCD of M and P is 1,

Bézout’s identity guarantees existence of integers x and y such that Mx+Py=1. A quick google search would reveal that the Extended Euclid’s Algorithm can be used to get values of x and y. Detailed implementation of Extended Euclid’s algorithm is easily available on the web and hence left as a (trivial) exercise to the reader. Once we get x, observe that k = xN. Of course, make sure to adjust the value of xN (if needed) to bring it in the set {0,1,…,P-1}. The solution to the equation (B) can then be obtained by plugging values M = A and N = -B in the above discussion. Similarly solution of (E) can be obtained by plugging M = 2A and N = u-B in the above discussion.

**Task**: Find all possible solutions to the congruence Mw^{2} ≡ N (mod P)

**Constraints**: P is prime, 0 < M,N,w < P

Since the table-approach worked in the previous case, let’s use the same again.With M = 4, N = 3 and P = 11, we get following results:

w mod P | w^{2}mod P |
(Mw^{2})mod P |
(Mw^{2}-N)mod P |

0 | 0 | 0 | 8 |

1 | 1 | 4 | 1 |

2 | 4 | 5 | 2 |

3 | 9 | 3 | 0 |

4 | 5 | 9 | 6 |

5 | 3 | 1 | 9 |

6 | 3 | 1 | 9 |

7 | 5 | 9 | 6 |

8 | 9 | 3 | 0 |

9 | 4 | 5 | 2 |

10 | 1 | 4 | 1 |

Observe that unlike the previous table, the columns in this table don’t have all the values. Taking an example of second column (w^{2}mod P ), we see that some values (like 2) are not present, whereas some other values (like 4) are repeated. More specifically –

- if we ignore the starting 0 in this column, then the column looks symmetric – The values 1,4,9,5,3 repeat in the reverse order.
- All values in the first half of this column are distinct.

It is easy to see that these two observations will always hold. And the proofs are very trivial:

- Observe that (P-w)
^{2}≡ w^{2}(mod P). Thus, for any w, numbers w^{2}and (P-w)^{2}would evaluate to the same result mod P. This means that the column (Mw^{2}mod P) would always be symmetric around the center. - To see why all the values in the first half of the column would be distinct, let us assume that two values of w, say w1 and w2, (WLG let w1 > w2) both occurring in the set {0,1,…,(P-1)/2} evaluate to the same result in column-2, i.e., let Mw1
^{2}≡ Mw2^{2}(mod P). This would mean that P|(w1^{2}-w2^{2}), which would in turn mean P|(w1+w2) or P|(w1-w2). But this is clearly a contradiction, as both (w1+w2) and (w1-w2) are less than P but greater than zero.

Moral of the story – There are exactly (P-1)/2 *distinct* values for (w^{2}mod P) with 0 < w < P, and each of these values occurs twice. (Notice the strict inequality “0 w”. This is because when w=0, the value in column-2 is 0 which is the only value that doesn’t repeat).

It is not hard to prove exactly the same results for columns-3 and 4 also. The proofs are very trivial, and are left as an exercise to the reader.

What all this means is that the congruence Mw^{2} ≡ N(mod P) may or may not have a solution. Further, if it has a solution, say w = k , then there will be exactly one more solution, given by w = (P-k). In other words, the congruence Mw^{2}≡ N (mod P) has either 0 or 2 solutions.

So the entire discussion for the “quadratic congruence case” boils down to two fundamental questions:

- How do we know whether Mw
^{2}≡ N (mod P) has a solution or not? - If there is a solution, how do we find it?

Interestingly, any web search with this or related questions will certainly end up in references on quadratic residues. Looks like good time to throw-in some theory.

Consider a quadratic congruence x^{2}≡ m(mod n) with 0≤m<n. In mathematical jargon, the number m is called **quadratic residue modulo n**, if there exists some x that satisfies this congruence. If there is no x that can satisfy this congruence, then m is called **quadratic non-residue modulo n**.

For example, with m = 9 and n = 15, observe that x = 12 satisfies this congruence, and hence we say that 9 is a quadratic reside modulo 15. Similarly, 4 is also a quadratic residue modulo 15, since x = 2 satisfies the congruence x^{2}≡4(mod 15). On the other hand, there is no x for which x^{2}≡11(mod 15), and hence 11 is a “quadratic non-residue” modulo 15. As another example, observe that 0,1 and 4 are the only quadratic residues modulo 8.

Interestingly, note that it is only the terminology that is new here – the underlying concept is very much close to what most of us would have already studied (hopefully!). For example, we all know that every square is of the form 4k or 4k+1. (Proof is trivial, left as an exercise to the reader). This means that x^{2}≡v(mod 4) has a solution only when v = 0 or 1. In other words, the only quadratic residues modulo 4 are 0 and 1. Taking another example, we (definitely) know that a square always end in 0,1,4,5,6 or 9. That is to say, the congruence x^{2}≡v(mod 10) has a solution only when v belongs to the set {0,1,4,5,6,9}. Stated differently, the set of quadratic non-residues modulo 10 is {2,3,7,8}.

Thus, in the simplest terms – A number m is a called as **quadratic residue mod n** if a square can take the form (nk+m) for some integer k.

Finally observe that in the current case, we are only interested in finding quadratic residues modulo a prime number. More specifically, we want to find –

- if x
^{2}≡a (mod p) has a solution for a given a - Find the value of x if this equation has a solution.

The first part is somewhat easy. Recollecting

Fermat’s little theorem, we know that x^{p-1}≡1 (mod p) when x < p. Thus, (x^{2})^{(p-1)/2}≡1 (mod p). In other words, x^{2}≡a(mod p) would have a solution iff a^{(p-1)/2}≡1 (mod p).

Thus, in the current context, to check whether Mw^{2} ≡ N(mod P) has a solution, we multiply throughout by M to get the congruence (Mw)^{2} ≡ MN(mod P), and then use the above test with a=MN (and x = Mw)

(An exercise for the reader- Prove xor disprove : a^{(p-1)/2 }will either be congruent to 1 or -1 (mod P) where P is an odd prime and 0 < a < P).

This brings us to the last part of the discussion – The procedure for actually finding the value of a quadratic residue (provided it exists). This is the place where most of us would again do a web search, and would certainly come up with Shank-Tonelli algorithm. This algorithm is actually a procedure for solving quadratic congruences of the form x^{2}≡n (mod P) where P is an odd prime and n is a quadratic residue modulo P. (Proving the correctness of this algorithm is quite complicated and beyond the scope of this tutorial.) We just re-state this algorithm at the end of this tutorial for the sake of completeness.

Thus we have now answered both the questions, and effectively learnt how to tackle quadratic congruences. This completes the discussion of the problem of quadratic equation.

- The basic reason why I stated this problem as an “easy” problem in the beginning is that it doesn’t require a person to “think a lot”, or think “out of the box” or “discover” some complex logic. All that is needed is a little bit of playing around, some familiarity with Number Theory, and well-developed Google-search skills. That in fact explains why such problems are actually a feast in programming competitions.
- The Shank-Tonelli algorithm to solve x
^{2}≡ a (mod P) where P is an odd prime is as follows:- Express (p-1) as a product of an odd number and a power of 2 – Let p-1 = 2
^{n}k - Let q be a quadratic non-residue modulo P. (To find q, set initial value of q to 2 and keep on incrementing till you don’t get q
^{ }satisfying q^{(p-1)/2}≡ -1 (mod p) - Let t = a
^{(k+1)/2 }% p and let r = a^{k}%p - If r≡1 (mod p) then return t as answer (i.e. algorithm ends).
- Else find v = smallest power of 2 such that r
^{v}≡1(mod p). (Let v = 2^{i}) - Let e = 2
^{(n-i-1)} - Let u = q
^{(ke)}%P. - Set t = (t*u)%P
- Set r = (r*u*u)%P and goto step (4)

- Express (p-1) as a product of an odd number and a power of 2 – Let p-1 = 2

This completes the discussion on the problem “Quadratic Equations”. To see actual solutions based on this idea, refer Ashutosh’s Solution, or Josh Metzler’s solution or my solution.

Greetings,

We are very excited to announce the winners of our first weekend Mini Challenge

**Winners :**

**Top 3 (India):**

1st – Anshuman Singh (1.000)

2nd – Pratik Tandel (0.946)

3rd – Kunal Jain (0.907)

**Top 3 (US):**

1st – Rahul Garg (0.99)

2nd – Balakrishnan Varadarajan (0.985)

3rd – Josh Metzler (0.983)

**Statistics:**

The problem is now available in the practice area. The test cases for the problem will be made public soon.

Here are some additional statistics about the contest:

Length of Contest |
Unique Visitors |
Unique Participants |
Total Number of Submissions |
Percentage of user who have solved at least one problem |

2 days | 2280 | 63 | 2154 | 59% |

Country | Total Participants |

IN | 47 |

US | 13 |

Rest of World | 3 |

**Feedback:**

This was our first short contest. All our past contests have spanned over at least 10 days while this one was held over just one weekend. We would like your feedback regarding the contest and its format. If you faced any issues with our site or the contest problem, do let us know.

Also, if you have any kind of feedback related to the contest or otherwise, feel free to comment.

**The September Challenge :**

Our monthly competition for September will start on the 1st of September at 15:00 (IST). So stay tuned

Regards,

Aniruddha.

Note : Because of some server-side issues we have disabled the chat feature as of now. It will be back as soon as we get things in place on the server.

Greetings Everyone !

In a bid to encourage interaction among users, we have introduced a shout-out box where people can chat or discuss anything that interests them. Currently, the shout-out box is visible at the bottom of the screen and the last two messages received are displayed. When you click on it, you get a bigger shout-out box where you can type messages, if logged in.

We hope that you will not misuse this functionality. You can get back to us with the feedback at admin@codechef.com or by leaving a comment on this post.

Happy Chatting !

Regards,

Aniruddha.

Greetings everyone !

We have just shifted our site to a CMS named Drupal. The major reasons for doing this is the amount of flexibility it offers in terms of introducing new features and modules. The new site was launched a few hours ago and I am sure most of you have figured out that something has changed We want your feedback on this. Also, if you face any issues, or find broken links, you can post them as a comment or get back to us at admin@codechef.com

Looking forward to your take on our new site. Happy coding.

Regards,

Aniruddha.

The problem Product of Divisors asks us to find the last 4 digits of the product of all the divisors of a number. So, suppose we are given a number like 12. The divisors for any number which is not a perfect square will occur in pairs. So, the divisors for the number 12 will be in the following pairs (1,12), (2,6), (3,4). Now, according to the problem statement, we are not to consider the number 12 while computing the answer, so effectively, we can remove the first pair. So, the answer we need will be the product of the numbers 2,6,3,4 which equals 144. Now, the purpose of grouping the numbers in pairs was to show that the product of the numbers in each pair is 12. So, if for a number N, which is not a perfect square, having D divisors, we can always group them into D/2 pairs such that the product of each pair is the original number N. Thus, we effectively transform the answer into N*N*..*N (D-2)/2 times. Thus, The answer in this case becomes N ^ (D/2) where ^ represents the power function and D represents the number of divisors. Thus, for the number 12, the number of divisors is 6, so the answer is 12 ^ ((6-2)/2) = 12 ^ 2 = 144.

Now, let us take the case of a number which is a perfect square. Consider the number 36 which is a perfect square. The divisors of 36 are 1,36,2,18,3,12,4,9,6. So now, if we start grouping them into pairs such that the product of each pair is 36, we get the following pairs (1,36), (2,18), (3,12), (4,9), (6,6). Now, we see that the divisor 6 needs to be repeated to form the pairs of the sort mentioned previously. We have 9 divisors for the number 36. As earlier, we remove 2 of the divisors, that is, the pair (1,36) as the problem statement asks us not to consider the number N while taking the product. Thus we start grouping the numbers into pairs again : (2,18), (3,12), (4,9) and we get one divisor 6 which is left without a divisor to pair up with. So, consider that we group up 6 with 6 itself to get another pair which gives us the value 36. So, the total product will be (36 ^ (number of pairs))/6. So, effectively if we have to calculate the product of divisors for a number N which is a perfect square, our equation becomes N^((D-2)/2) which is N^(D-2)/2. In the earlier case, as D would always be even, D-2 would be even and (D-2)/2 would be an integer. But in this case, as N is a perfect square, (D-2) is odd. We can reframe this as (N^(1/2))^(D-2). Now, as N is a perfect square, N^(1/2) will be an integer. So the answer in this case becomes sqrt(N)^(D-2).

So, we can see that given a number, we can find the required answer using the expressions mentioned above. So now, the only thing left to do is to find the number of divisors. Now, let us see how to calculate the number of divisors of a particular number. Suppose the number N is factorized into its prime factors and their powers as p1^a1 * p2^a2 * … * pn^an. Then, the number of divisors of the number N including 1 and N are (a1+1)*(a2+1)*…*(an+1). Let us see why this is so. Take the case that N is a prime number, then the prime factorization of N can be p1^1 where p1=N. N has 2 divisors 1 and N so the answer is (1+1) which is 2. Now consider a number N which has prime factorization p1^a1 * p2^a2 * … * pn^an. Now, suppose a number B which equals N*P where P is a prime number. Now, the prime factorization of B becomes p1^a1 * p2^a2 * … * pn^an * p^1. Suppose the number N had X divisors. B equals N*P, so all divisors of N are divisors of B. Also, if T is a divisor of B, then so is P*T. Thus, we see that the number of divisors in this case has doubled. That is because of the introduction of P^1 in the sequence, the number of divisors has become X * (1+1). This can easily be extended to introduction of P^Z in the sequence to show that because of this introduction, the number of divisors is increased by a factor (Z+1).

So, now we know how to calculate the number of divisors of a number. We also know that once we know the number of divisors of a number, we can find the required answer using the formulae we derived. But, there is a small catch here. The number N can be pretty large and we need to find the power of N raised to a number which can be a about 100. Also, we need to do this for about 300000 numbers. If we calculate the power of the number modulo some value using an iterative function that iterates over the value of the exponent, our code won’t run within time. We can use a nice little trick here to calculate the value of (a^b)%p by using the observation that if ‘b’ is even, then a^b = a^(b/2) * a^(b/2) and if ‘b’ is odd, a^b = b*pow(a,b-1). Using this, we can calculate the power of a number pretty quickly taking about log(exponent) iterations.

` `

```
Thus, the rough outline of the required code would be something as follows :
Start
Precompute all primes below 500000
Precompute what numbers below 500000 are perfect squares and their squareroots
Take in number of test cases
While there exists a test case we haven't processed
Take in the number.
Find the number of divisors.
Calculate the answer using the formulae we derived.
Take the remainder with 10000 while calculating the answers.
Take care to make sure that we print the last 4 digits correctly with necessary number of 0s. Simply taking modulo 10000 will not work.
Print the answer
Stop
```

` `

We leave it to the reader to handle the part where the last 4 digits have to be correctly displayed.

We’re very excited about our latest community initiative – the CodeChef TechTalks. CodeChef TechTalks are India’s premier invitation-only geek symposia. The purpose of CodeChef TechTalks is to promote technical education and knowledge sharing by making internationally renowned speakers accessible to the best software professionals in India.

For the first edition we will be covering three cities – Mumbai, Bangalore and Hyderabad from September 10th-12th. We have Lisa Crispin and Owen Rogers flying down especially to deliver their sessions along with Bhavin Turakhia.

You can find complete details of the event as well as criteria for eligibility here. Like everything else on CodeChef, the TechTalks are not-for-profit. If you think your company can host or sponsor the event then do let them know about us. You can find more information regarding this here.

Spread the word about CodeChef TechTalks, go ahead and share this blog post!

- Five Problems A Day, Kept The Worries At Bay For Cleartax Intern Avjot Singh
- Thrice the coding fun for school students this October
- How Amit Upadhyay got placed at Cleartax
- A brand new CodeChef API – Happy Independence Day from CodeChef.
- SnackDown is here!

- About (14)
- ACM ICPC (21)
- Announcement (294)
- API (1)
- Campus Chapters (7)
- CCDSAP (2)
- Certification (4)
- College Contests (9)
- Contests (271)
- Events (54)
- FAQ (1)
- Features (49)
- Interviews (23)
- Languages (1)
- Meetup (4)
- Open Source (1)
- Practice Problems (8)
- Prizes (20)
- Problems (7)
- ProblemSetting (1)
- Programmer of the Month (34)
- Schools (11)
- SnackDown (2)
- Tech Talks (23)
- Tutorials (30)
- Uncategorized (1)
- Volunteers (3)
- Winners (119)

- Rajbir Singh on ACM ICPC Chennai Onsite Contest 2016 – Live Updates
- hansika hans on Important announcement concerning rating changes following plagiarism
- Harsimran Singh on The Cheating Cases Saga
- Harsimran Singh on The Cheating Cases Saga
- sarovar ram on The Cheating Cases Saga

- October 2018
- September 2018
- August 2018
- July 2018
- June 2018
- April 2018
- March 2018
- February 2018
- January 2018
- December 2017
- November 2017
- September 2017
- August 2017
- July 2017
- June 2017
- March 2017
- February 2017
- January 2017
- December 2016
- November 2016
- October 2016
- September 2016
- August 2016
- July 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- July 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009

© 2009, Directi Group. All Rights Reserved.