Поле за модулем#12317

Поле за модулем (Розбір)

Число $c$ \sqrt{c} ірраціональне, тому обчислювати вираз у дійсних числах немає сенсу: при $n$ до $1 0^{18}$ 10^{18} це неможливо через точність. Зауважимо, однак, що будь-який цілий степінь числа $a + b c$ a + b\sqrt{c} знову має вигляд $x + y c$ x + y\sqrt{c}, оскільки $c \cdot c = c$ \sqrt{c} \cdot \sqrt{c} = c. Таким чином, обчислення слід виконувати в розширеному полі:

Z_{p} (c) = {x + y c ∣ x, y \in Z_{p}}

Z_p (\sqrt{c}) = \{ x + y \sqrt{c}~|~x,y \in Z_p\}

Правила операцій:

Додавання

(x_{1} + y_{1} c) + (x_{2} + y_{2} c) = (x_{1} + x_{2}) + (y_{1} + y_{2}) c

(x_1 + y_1 \sqrt{c}) + (x_2 + y_2 \sqrt{c}) = (x_1 + x_2 ) + (y_1 + y_2) \sqrt{c}

Множення

(x_{1} + y_{1} c) \cdot (x_{2} + y_{2} c) = (x_{1} x_{2} + c y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) c

(x_1 + y_1 \sqrt{c}) \cdot (x_2 + y_2 \sqrt{c}) = (x_1 x_2 + cy_1 y_2) + (x_1 y_2 + x_2 y_1 ) \sqrt{c}

Після визначення операції множення елементи поля $Z_{p} (c)$ Z_p (\sqrt{c}) можна підносити до степеня стандартним методом швидкого піднесення до степеня за час $O (l o g_{2} n)$ O(log_2n). Це дозволить обчислити $(a + b c)^{n} m o d p$ (a + b \sqrt{c})^n~mod~p.

Приклад

У першому прикладі

(2 + 5)^{2} m o d 17 = (4 + 45 + 5) m o d 17 = 9 + 45

(2 + \sqrt{5})^2~mod~17 = (4 + 4 \sqrt{5} + 5)~mod~17 = 9 + 4 \sqrt{5}

Розглянемо другий приклад:

(3 + 25)^{10} m o d 17

(3 + 2 \sqrt{5})^{10}~mod~17

Нехай $x = 3 + 25$ x = 3 + 2 \sqrt{5}. Обчислимо його степені:

x^{2} = (3 + 25)^{2} m o d 17 = (9 + 125 + 20) m o d 17 = 12 + 125 x^{4} = (12 + 125)^{2} m o d 17 = (144 + 2885 + 720) m o d 17 = 14 + 165 x^{8} = (14 + 165)^{2} m o d 17 = (196 + 4485 + 1280) m o d 17 = 14 + 65

x^2 = (3 + 2 \sqrt{5})^2~mod~17 = (9 + 12 \sqrt{5} + 20)~mod~17 = 12 + 12 \sqrt{5} \\ x^4 = (12 + 12 \sqrt{5})^2~mod~17 = (144 + 288 \sqrt{5} + 720)~mod~17 = 14 + 16 \sqrt{5} \\ x^8 = (14 + 16 \sqrt{5})^2~mod~17 = (196 + 448 \sqrt{5} + 1280)~mod~17 = 14 + 6 \sqrt{5}

Тепер можна обчислити результат:

x^{10} = x^{8} \cdot x^{2} = (14 + 65) (12 + 125) m o d 17 = (168 + 725 + 1685 + 360) m o d 17 = 1 + 25

x^{10} = x^8 \cdot x^2 = (14 + 6 \sqrt{5})(12 + 12 \sqrt{5})~mod~17 = \\ (168 + 72 \sqrt{5} + 168 \sqrt{5} + 360)~mod~17 = 1 + 2 \sqrt{5}

Реалізація алгоритму

Оголосимо структуру $N u m$ для зберігання числа вигляду $x + y c$ x + y \sqrt{c}.

struct Num
{
  long long x, y; // x + y*sqrt(c)
};

Реалізуємо множення в полі $Z_{p} (c)$ Z_p (\sqrt{c}). Функція mult повертає добуток чисел $a$ і $b$ .

Num mult(Num &a, Num &b)
{
  Num res;
  res.x = (a.x * b.x + c * a.y % p * b.y) % p;
  res.y = (a.x * b.y + a.y * b.x) % p;
  return res;
}

C++

Функція pow реалізує піднесення до степеня $ba s e^{n}$ base^n, де $ba se$ — число в полі $Z_{p} (c)$ Z_p (\sqrt{c}).

Num pow(Num base, long long n)
{
  Num res = { 1, 0 }; // одиниця поля
  while (n > 0)
  {
    if (n & 1)
      res = mult(res, base);
    base = mult(base, base);
    n >>= 1;
  }
  return res;
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &n, &p);

Ініціалізуємо початкове число $s t a r t = a + b c$ start = a + b \sqrt{c}.

Num start = { a % p, b % p };

Обчислюємо та виводимо відповідь $an s = s t a r t^{n} m o d p = (a + b c)^{n} m o d p$ ans = start^n~mod~p = (a + b \sqrt{c})^n~mod~p.

Num ans = pow(start, n);
printf("%lld %lld\n", ans.x, ans.y);