RakibJoy's blog

Overflow But Accepted !
By RakibJoy, history, 2 years ago, In English

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.

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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$$$.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

Actually, this is UB. Why is it accepted?

Godbolt compiler explorer shows the code is compiled into this:

Assembler code

AFAIK function std::pow returns double. Then it is converted into long long int using instruction cvttsd2si (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 than b, and result is correct.

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

++, 


n = int(input())
m = int(input())

print(m % (pow(2, n)))

This is also accepted, I am confused.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    python handles big integers itself, so there is no case of overflow

    → Reply