When I was doing 1207F - Remainder Problem, I don't know why my program got TLE. Then this ONE trick cut 1 second off my program. You can see this video for more information: https://www.youtube.com/watch?v=ssDBqQ5f5_0. When the compiler compiles x/9
, the code roughly converts to ((long long)954437177*x)>>33
. Division is a much more expensive operation than multiplies and shifts. But what's the special constant 954437177
? It's ⌈2339⌉. So we have this identity which is vaild for every 0≤a<231,0<x<231:
You can clearly see how this speeds up 1207F: 244531668, 244540601. Note that gcc also does this trick on 64 bits.
After brute forcing with a=231−1 I got this new, fixed identity. This should work for all a (while the old one does not).