Hi codeforces, as there is no editorial, hope someone can help to solve problems D, E, F from BSUIR Open X. Reload. Semifinal
I am personally very interested in problem D, as I can't compute something like $$$2 \hat{}\hat{} {10^{18}}$$$ mod $$$(10^9 + 7)$$$ even by hand.
I'm interesting problem C,But i can't solve up to now,If you solved problem C, Could you explain your idea?
I solved this problem, I decided this problem, now I honestly don't remember how it is solved, but here's the code, you can try to figure it out:
From Fermat's little theorem we have.
image upload
From merging the first two statements we have:
Multiplying both sides by a^(p — 1) any number of times, we have
multiplying both sides by some t:
or equivalently:
With this trick we can compute extremely large exponents under some modulo, precisely by taking the module of p — 1 of the exponent.
Problem D can be solved using following two things:
Formula 1:
, where $$$\phi(m)$$$ — Euler's totient function. This is extension of Euler's theorem.
Formula 2:
, where $$$C \approx 2 \cdot \log_2(m)$$$.
This two observations allows you to calculate $$$^{b}a \bmod m$$$ in time $$$O(log^2(m))$$$.