Modul üzrə sahə#12317

Modul üzrə sahə (Həll təhlili)

$c$ \sqrt{c} ədədi irrasionaldır, buna görə də ifadəni həqiqi ədədlərdə hesablamaq mənasızdır: $n$ $1 0^{18}$ 10^{18}-dək olduqda bu, dəqiqliyə görə mümkün deyil. Lakin qeyd edək ki, $a + b c$ a + b\sqrt{c} ədədinin istənilən tam qüvvəti yenidən $x + y c$ x + y\sqrt{c} formasında olur, çünki $c \cdot c = c$ \sqrt{c} \cdot \sqrt{c} = c. Beləliklə, hesablamaları genişləndirilmiş sahədə aparmaq lazımdır:

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

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

Əməliyyat qaydaları:

Toplama

(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}

Vurma

(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}

Vurma əməliyyatı müəyyən edildikdən sonra $Z_{p} (c)$ Z_p (\sqrt{c}) sahəsinin elementlərini standart sürətli qüvvətə yüksəltmə metodu ilə $O (l o g_{2} n)$ O(log_2n) vaxtında qüvvətə yüksəltmək olar. Bu, $(a + b c)^{n} m o d p$ (a + b \sqrt{c})^n~mod~p ifadəsini hesablamağa imkan verəcək.

Nümunə

Birinci nümunədə

(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}

İkinci nümunəyə baxaq:

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

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

Tutaq ki, $x = 3 + 25$ x = 3 + 2 \sqrt{5}. Onun qüvvətlərini hesablayaq:

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}

İndi nəticəni hesablaya bilərik:

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}

Alqoritmin realizasiyası

$x + y c$ x + y \sqrt{c} formasında ədədi saxlamaq üçün $N u m$ strukturunu elan edək.

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

$Z_{p} (c)$ Z_p (\sqrt{c}) sahəsində vurmanı reallaşdıraq. mult funksiyası $a$ və $b$ ədədlərinin hasilini qaytarır.

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 funksiyası $ba s e^{n}$ base^n qüvvətə yüksəltməsini reallaşdırır, burada $ba se$ — $Z_{p} (c)$ Z_p (\sqrt{c}) sahəsindəki ədəddir.

Num pow(Num base, long long n)
{
  Num res = { 1, 0 }; // meydanın vahidi
  while (n > 0)
  {
    if (n & 1)
      res = mult(res, base);
    base = mult(base, base);
    n >>= 1;
  }
  return res;
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$s t a r t = a + b c$ start = a + b \sqrt{c} başlanğıc ədədini ilkinləşdiririk.

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 cavabını hesablayıb çap edirik.

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