Блог пользователя ZergTricky

Editorial for BSUIR X semifinals
Автор ZergTricky, история, 20 месяцев назад, По-английски

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.

Обсуждение BSUIR Open X. Reload. Semifinal
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm interesting problem C,But i can't solve up to now,If you solved problem C, Could you explain your idea?

→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
    ← 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;
    → Ответить
»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

From Fermat's little theorem we have.

mala-fermaova
image upload
lagrida-latex-editor-3

From merging the first two statements we have:

lagrida-latex-editor-4

Multiplying both sides by a^(p — 1) any number of times, we have

lagrida-latex-editor-5

multiplying both sides by some t:

lagrida-latex-editor-6

or equivalently:

lagrida-latex-editor-7

With this trick we can compute extremely large exponents under some modulo, precisely by taking the module of p — 1 of the exponent.

→ Ответить
»
20 месяцев назад, # |
← 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))$$$.

→ Ответить