### ZergTricky's blog

By ZergTricky, history, 16 months ago,

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.

• +8

 » 16 months ago, # |   0 I'm interesting problem C,But i can't solve up to now,If you solved problem C, Could you explain your idea?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 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: ll a, b, x; cin >> a >> b >> x; if (x <= a) { cout << a + 1 - b + 1 << endl; ret; } cout << x - b + 1 << endl; 
 » 16 months ago, # |   0 From Fermat's little theorem we have.From merging the first two statements we have:Multiplying both sides by a^(p — 1) any number of times, we havemultiplying 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.
 » 16 months ago, # | ← Rev. 4 →   +5 Problem D can be solved using following two things:Formula 1: $a^b \bmod m = \begin{cases} a^{b}, & \text{if } b < \phi(m) \\ a^{(b \bmod \phi(m)) + \phi(m)}, & \text{if } b \ge \phi(m) \end{cases}$, where $\phi(m)$ — Euler's totient function. This is extension of Euler's theorem.Formula 2: $^{b}a \bmod m =~^{\min(b, C)}a \bmod m$, 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))$.