### RakibJoy's blog

By RakibJoy, history, 6 weeks ago, How my friends submission 80262789 for this problem 913A - Возведение в степень по модулю is accepted? Here 1 ≤ n ≤ 10^8 and he used pow() function for the value of 2^n.  Comments (5)
 » 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$.
 » 6 weeks ago, # | ← Rev. 2 →   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
 » 6 weeks ago, # | ← Rev. 2 →   Actually, this is UB. Why is it accepted?Godbolt compiler explorer shows the code is compiled into this: Assembler code.LC0: .string "%lld%lld" .LC1: .string "%lld\n" main: push rbp mov rbp, rsp sub rsp, 32 lea rdx, [rbp-32] lea rax, [rbp-24] mov rsi, rax mov edi, OFFSET FLAT:.LC0 mov eax, 0 call __isoc99_scanf mov rax, QWORD PTR [rbp-24] mov rsi, rax mov edi, 2 call __gnu_cxx::__promote_2::__value>::__type, __gnu_cxx::__promote::__value>::__type>::__type std::pow(int, long long) cvttsd2si rax, xmm0 mov QWORD PTR [rbp-8], rax mov rax, QWORD PTR [rbp-32] cqo idiv QWORD PTR [rbp-8] mov QWORD PTR [rbp-16], rdx mov rax, QWORD PTR [rbp-16] mov rsi, rax mov edi, OFFSET FLAT:.LC1 mov eax, 0 call printf mov eax, 0 leave ret 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.
 » 6 weeks ago, # | ← Rev. 3 →   ++, n = int(input()) m = int(input()) print(m % (pow(2, n))) This is also accepted, I am confused.
•  » » python handles big integers itself, so there is no case of overflow