How my friends submission 80262789 for this problem 913A - Modular Exponentiation is accepted? Here 1 ≤ n ≤ 10^8 and he used pow() function for the value of 2^n.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
How my friends submission 80262789 for this problem 913A - Modular Exponentiation is accepted? Here 1 ≤ n ≤ 10^8 and he used pow() function for the value of 2^n.
Name |
---|
If you check value of the $$$power$$$ for large $$$n$$$, you will see that it is equal to $$$LLONG$$$_$$$MAX$$$ (This is probably undefined behavior). Since, $$$m$$$ itself is bounded by $$$1e8$$$, the remainder is $$$m$$$ for all divisors greater than $$$m$$$.
Seems like after a certain power, 2^n gets stuck at -9223372036854775808 (-2^63, the limit of ll), and so taking any ll its modulo won't change it, which is exactly what we want for big n's
Actually, this is UB. Why is it accepted?
Godbolt compiler explorer shows the code is compiled into this:
AFAIK function
std::pow
returnsdouble
. Then it is converted intolong long int
using instructioncvttsd2si
(convert signed double to signed integer).And documentation for that instruction (can be seen on Godbolt too) says:
If a converted result exceeds the range limits of signed quadword integer (in 64-bit mode and REX.W/VEX.W/EVEX.W = 1), the floating-point invalid exception is raised, and if this exception is masked, the indefinite integer value (80000000_00000000H) is returned.
So value
power
is way bigger thanb
, and result is correct.++,
This is also accepted, I am confused.
python handles big integers itself, so there is no case of overflow