17D - Notepad my submission history is embarrassing
Doing a number theory tour right now haha, this problem just wants you to compute $$$(b-1)\cdot b^{n-1} \bmod c$$$.
Intuitively, I tried to use a simple repeated squaring technique, but always got TL around test case 27 (in which b and c are around 10k digits). I thought python's builtin integer implementation was to blame, and some fiddling shows that python's Decimal module has a pretty slow division (they don't optimize for integers), so I switched to Java's BigInteger, which still is slow. Then it came to me the repeated squaring approach is O(L^2) where L is length of the exponent, not L*log(L) as I initially thought. No wonder it failed then because b and n can be 10^6 digits. On the good side, c is not so large, so Euler's totient theorem can help: just replace n-1 with $$$n-1 \bmod \phi(c)$$$. (You can compute the remainder of a large string modulo a fairly small number by going over its digits RTL, keeping track of the remainder of $$$10^i$$$.)
But this only works when b and c are coprime. For the non-coprime scenario, initial suggestions I found seemed complicated (computing gcd etc). Then I came across a note saying that in that case, it is still ok if you're willing to give in another $$$\phi(n)$$$. More precisely,
Stronger statements hold but I found the current form the easiest to implement since now nbcs about coprimality/gcd. So here's the recipe:
- Input b,n,c. Store b,n as strings and c as a number
- Compute r=(b-1)%c and s=b%c by looping on the digits (do s first to avoid string subtraction)
- Factorize c and compute $$$\phi(c)$$$
- We want t to satisfy $$$s^t\equiv s^{n-1}$$$. From the discussion we can set t=(n-1)%phi(c), and if this is not n-1 then add $$$\phi(c)$$$ to t.
- Use fast exponentiation to find (r*s^t) % c. This time it's really fast, because r,s,t,c are all within 2^31.
This approach would finish all the test cases within 300ms using PyPy, meanwhile still TLing with python, LOL.
