That one is OK. The problem here is a different one: that 25^12 cannot be represented exactly in a double. The set of possible values for a double is not a superset of possible values of a long long.

In this particular contest, one could hack a pow() solution by finding 2 numbers in different bases that should give the result "=". Preferably something large. That way, if one of the numbers becomes off-by-1 because of the pow() "bug", it will give a different result.

I think the judge is very sensitive to this, because my every hack attempt at that kind of solution worked (and I hacked like 7 solutions), so I don't think one can get away with it on "luck"

Don't forget to try your case at "custom invocation" first.

I'm not sure what is the part you "don't get".

Obviously all these functions are evaluated numerically. It's usually way more complicated than just a simple sum of a Taylor series, but that is still a good visualization. (Newton iteration is a slightly better one because it tends to converge faster.)

However. Part of the problem here is that the floating-point standard requires conforming pow() implementations to be as precise as they can be, but this is clearly not the case in case of the implementation used by the Codeforces g++ compiler. Once again in other words: Codeforces pow is not as precise as it can be.

Regardless of what the precision of your internally computed result, it should never return 99.999999 if it is given the exact inputs 10 and 2. The value 100.0 can be represented in a double exactly, and it is closer to the exact answer -- because it is the exact answer.

In this area it's usually possible to prove stuff like "if I take any value x from this interval and I do three iterations of this numeric algorithm, I will get the result that is as precise as possible within the precision of doubles". (A very simple example of this would be: if I use binary search on the interval [1,2], after 100 iterations I can have the answer as precise as doubles allow.) I suspect that the pow() at codeforces sometimes does too few iterations / has some other similar implementational issue. Another possibility would be that it doesn't use a higher precision (80-bit floats) internally and that screws it up somehow.

It's certainly possible to implement pow() in a better way, as witnessed by the fact that it works on other platforms.

Thanks for the information :)

I have checked the same in g++ 5.2.1 on Kubuntu. It does also evaluate the first call to pow() at compile time, but it does obtain the correct value.

Well, unless you need the special cases such as power(0,10^9) and power(1,10^9), the O(log n) doesn't really matter for powers of standard integers, as the largest valid n is used in power(2,63) for unsigned long longs.

But yeah, power() is in O(log n) and that is useful because it can also be used as follows:

#include <bits/stdc++.h>
#include <ext/numeric>
using namespace std;
using namespace __gnu_cxx;

struct number {
    int value;
    number(int value=0) : value(value) {}
};

number operator*(const number &a, const number &b) {
    return (1LL * a.value * b.value) % 1000000007;
}

int main () {
    // outputs 514713417 == (2 ^ 1234567890) mod (10^9 + 7)
    cout << power( number(2), 1234567890 ).value << endl;
}

Not so rare. In CodeForces I saw tens of posts "why does my code get WA?" where the answer was "don't use built-in pow()".

I wonder that nobody mentioned nearbyint() function (in C99 standard).

llround() was mentioned, and it does nearly the same, but returns the integer, unlike nearbyint(), which is usually preferable.