I found a very strange thing in Educational Codeforces Round 50 F. Relatively Prime Powers.
First, here is a AC code written by me. https://codeforces.net/contest/1036/submission/42680029
And If you add a line "assert(val != 999999999999999956LL);", then this code will fail on test 3. It means test 3 has a case that num = 999999999999999956. https://codeforces.net/contest/1036/submission/42680073
But This is another AC code written by @alonefight, https://codeforces.net/contest/1036/submission/42657108. I ran it in my local environment and compared with my code. The result is surprised.
I used the test case as follow. 1 999999999999999956
My result is 999999998998996625 But @alonefight's result is 999999998998996624
I submitted his code and it still passed all test case. https://codeforces.net/contest/1036/submission/42680102
FYI, my environment is macbook, clion, c++14.
Can anyone tell me why this strange thing happened?
Auto comment: topic has been updated by txingml (previous revision, new revision, compare).
In custom test his code gives 999999998998996625 with g++14 but in Clang++17 Diagnostics it gives 999999998998996624. I think it is smth like undefined behavior
This is really strange. I've tested his code in custom test under Clang++17 Diagnostics. And look at this pictures scrt(n) gives 999999999, but if i comment one line that doesn't influence to the output it outputs 1000000000! first, second
I found another strange thing with codeforces g++14. If you run this code in custom test g++14 you will get that sqrt(n) yields different results 999999999 vs 1000000000
sqrt()
works in floating point. The result it returns may not precisely match the true value, and this is fine. If you need precise results, you should compute integer square root manually.Regarding the problem above, this is likely related: https://isocpp.org/wiki/faq/newbie#floating-point-arith2
Thank you all for replying my question.
sqrt(999999999999999956LL) will get 1000000000.0000000000 in my environment, and sqrt((long double)999999999999999956) will get 999999999.9999999780.
So it seems that if we need to use sqrt() and trucate result into integer, we must do some check. Such as: