I agree. They should make python (and all other slow languages for that matter) TLs flexible depending on the algo expected for the problem.
1 Like
1 upvote from my side. I had no idea before hosting this problem that python would time out. Setter(Myself) and Tester did wrote C++ code and believed that the multiplier would work fine! I personally do not like changing problem/time limit in running contest after it had a lot of submissions. If i had seen this issue when only 5/10 users had tried then i would have definitely changed the time limit. I thought it was not a serious issue and the guys will enjoy handling overflows in C/Java/C++.I apologize and promise that all my easy/simple/cakewalk problems will be solvable in python.Thanks 
8 Likes
When we say that a=b mod m (0<=b<m) we mean that the remainder when a is divided by m is b. This is equivalent to saying that there exists an integer q such that qm+b=a. We are trying to prove that if n/k=x mod m (0<=x<n, k>0), then n=xk mod mk and 0<=xk<mk. We know that n/k=x mod m is equivalent to saying that there exists a q such that qm+x=n/k. Multiplying by k, we see that (qk)m+xk=n. We see that this is equivalent to the statement we are trying to prove(with q’=qk and remainder xk), and that additionally 0<=xk<mk since 0<=x<m.
12 Likes
@achaitanyasai Can you please explain why this trick works from a mathematical point of view?
3 Likes
It’s the other way round it is when we divide a by m than b is the remainder.
Put s= 30t+y , expand s*(s+1)(2s+1)(-1+3s+3s^2)/30 , you will get what i did 
, a brute way of thinking if you stuck with overflows 
I implemented the same thing in JAVA and got TLE using Big integer…Can anyone justify why? … here’s the code CodeChef: Practical coding for everyone
@achaitanasai i am also eager to know why this is working…
this much googling and logical thinking is for you to do.
But here in your example the different values for [n/i] should be 5(sqrt(25)) but its actually 9. so how it proves the statement?
There would be 2*sqrt(n) - 1 different values…and to get them quickly we do it in 2 steps.
first go from i=1 to i=sqrt(n) and sum the terms i^4 * (n/i)…basically brute force over sqrt(n) values.
next you will see that as i gets bigger, the (n/i) starts repeating for many consecutive i’s and it will be in range sqrt(n) to 1…so too take advantage of this fact we do a little reverse thing. say x = (n/i), we iterate over x from sqrt(n) to 1 and try to find how many i’s might give this value x…again this will be done in o(sqrt(n))…so total complexity remains o(sqrt(n)).
2 Likes
The problem is that you have not reset the value of sum=0 for each test case…secondly this method will give tle
this trick is great however i couldn’t think of it so i just divided the numerator by 30 then used fmod , and that worked too.
When the number gets big, double loses precision and hence you do not get right answer also the your code is too slow to get AC