I dont know how by the same logic in c++ gives AC and the same logic in python gives WA 
.
Python solution link: Click Here
C++ solution link: Click Here
Can anyone justify this ? 
can mobius inversion be used for this problem
Yeah, c++ gave right answer, python gave wrong answer 
.
If you prefer video solution :
6 Likes
I was saying the same exactly on the comment section. This should have been fixed in the contest. Perfectly waisted my time. My code works on each test case. I have done random tests cases of all the powers from 2 to 18. But was only giving WA on TC <= 15 i.e Subtask 5.
The main error in python was
>>> a = sqrt(10 ** 18 - 1)
>>> a
1000000000.0
If we will see the people scoring 60. Most of them actually solved it correctly but just because of the precision error. Most of them are unable to get it AC completely. I myself submitted it more than 25 times but didn’t get more than 60. Also there is no reference answer to match your output for such high values for which brute code will take hours to solve.
2 Likes
yep, wasted so much time on this. Didn’t thought that issue is in the precision of sqrt function.
Sorry, what should have been fixed in the contest? Your wrong solution, or what? Obviously, if you received Wrong Answer verdict, this means that your code DO NOT work on each test case.
Maybe you guys should have tested on python as well beforehand as what else could have been done as it is a Wrong answer because of python error not ours.
Well, at first there are solutions in python which got AC. At second, as far as I know nobody guarantees that each problem must be solvable in python at all.
2 Likes
sqrt is not precise enough. I was getting WA, then i wrote a binary search to get the floor of the square root. But that was giving TLE, finally I tried sqrtl and that passed
Also this is your problem, not anybody else mistake, that you don’t know/understand how does your code work, and why it can be incorrect.
1 Like
For a big contest like this. and problem related to BigIntegers. I think it should be solved. as most people fails to understand the % MOD part.
Anyways it was a great contest at last I did get AC.
why are you initializing ans=n%mod in the main?
if n is a perfect power it would have already been present in some d[i] already.
My solution did not involve the Inclusion and Exclusion:
- Choose M=\lceil{N^{\frac13}}\rceil . For all x\leq M, sum up the contribution of all powers of x. In order to avoid overcounting, keep a track of all numbers \leq M which have already been taken care of beforehand(as a power of some smaller x). This way, one can never count any power more than once. Also, do NOT add the contribution of even powers which are more M^2.
2)Now note that for x>M, only x^2 can contribute to the sum as x^3>M^3>N. Also, the square of such an x is greater than M^2, and we have already excluded such even powers in 1),hence we can directly sum them up with the interval trick mentioned by @taran_1407.
For both the steps, the running time can be computed to be O(N^{\frac13}).
Is there no LaTeX support for replies?
There \ is
Just put $math here$
2 Likes
My bad, there was a typo in there, thanks!