Sahədə cəm#12318

Sahədə cəm (Həll təhlili)

Hesablamalar genişlənmiş sahədə aparılmalıdı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}

Tutaq ki, $x = a + b c$ x = a + b \sqrt{c}. Onda axtarılan məbləğ sonlu həndəsi silsilədir:

1 + x + x^{2} + x^{3} + ... + x^{n} = \frac{x ^{n + 1} - 1}{x - 1} = \frac{a}{b}

1 + x + x^2 + x^3 + ... + x^n = \frac{x^{n + 1} - 1}{x - 1} = \frac{a}{b}

Qalır $a = x^{n + 1} - 1$ a=x^{n+1} - 1 və $b = x - 1$ b=x-1 arasında $Z_{p} (c)$ Z_p (\sqrt{c}) sahəsində bölməni həyata keçirmək:

\frac{a}{b} = \frac{a _{x} + a _{y} c}{b _{x} + b _{y} c} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{( b _{x} + b _{y} c ) ( b _{x} - b _{y} c )} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{b _{x}^{2} - b _{y}^{2} c} = (a_{x} + a_{y} c) (b_{x} - b_{y} c) (b_{x}^{2} - b_{y}^{2} c)^{- 1}

\frac{a}{b} = \frac{a_x + a_y \sqrt{c}}{b_x + b_y \sqrt{c}} = \frac{(a_x + a_y \sqrt{c})(b_x - b_y \sqrt{c})}{(b_x + b_y \sqrt{c})(b_x - b_y \sqrt{c})} = \frac{(a_x + a_y \sqrt{c})(b_x - b_y \sqrt{c})}{b_x^2 - b_y^2 c} = \\ (a_x + a_y \sqrt{c})(b_x - b_y \sqrt{c}) (b_x^2 - b_y^2 c)^{-1}

Nümunə

Birinci nümunədə

i = 0 \sum 2 (2 + 5)^{i} m o d 17 = (1 + (2 + 5) + (9 + 45)) m o d 17 = 12 + 55

\sum_{i = 0}^2 (2 + \sqrt{5})^i~mod~17 = (1 + (2 + \sqrt{5}) + (9 + 4\sqrt{5}))~mod~17 = 12 + 5\sqrt{5}

Bu nümunəni formul ilə hesablayacağıq:

i = 0 \sum 2 (2 + 5)^{i} m o d 17 = \frac{( 2 + 5 ) ^{3} - 1}{( 2 + 5 ) - 1} = = \frac{( 8 + 12 5 + 30 + 5 5 ) - 1}{1 + 5} = \frac{37 + 17 5}{1 + 5} = \frac{3}{1 + 5} = \frac{3 ( 1 - 5 )}{( 1 + 5 ) ( 1 - 5 )} = \frac{3 ( 1 - 5 )}{- 4} = \frac{3 - 3 5}{13} = (3 - 35) \cdot 1 3^{- 1} = (3 - 35) \cdot 4 = 12 - 125 = 12 + 55

\sum_{i = 0}^2 (2 + \sqrt{5})^i~mod~17 = \frac{(2 + \sqrt{5})^3 - 1}{(2 + \sqrt{5}) - 1} = \\ = \frac{(8 + 12 \sqrt{5} + 30 + 5\sqrt{5}) - 1}{1 + \sqrt{5}} = \frac{37 + 17\sqrt{5}}{1 + \sqrt{5}} = \frac{3}{1 + \sqrt{5}} = \\ \frac{3(1 - \sqrt{5})}{(1 + \sqrt{5})(1 - \sqrt{5})} = \frac{3(1 - \sqrt{5})}{-4} = \frac{3 - 3\sqrt{5}}{13} = (3 - 3\sqrt{5}) \cdot 13^{-1} = (3 - 3\sqrt{5}) \cdot 4 = \\ 12 - 12\sqrt{5} = 12 + 5\sqrt{5}

İkinci nümunədə

i = 0 \sum 10 (3 + 25)^{i} m o d 17 = 15 + 65

\sum_{i=0}^{10} (3 + 2\sqrt{5})^i~mod~17 = 15 + 6\sqrt{5}

Alqoritmin reallaşdırılması

modpow funksiyası $a^{k} m o d p$ a^k~mod~p dəyərini hesablayır.

long long modpow(long long a, long long k, long long p)
{
  long long res = 1;
  a %= p;
  while (k)
  {
    if (k & 1) res = res * a % p;
    a = a * a % p;
    k >>= 1;
  }
  return res;
}

C++

Num strukturu $x + y c$ x + y \sqrt{c} formasında rəqəmləri saxlamaq üçün elan edək.

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

$Z_{p} (c)$ Z_p (\sqrt{c}) sahəsində toplama əməliyyatını reallaşdırırıq. add funksiyası $a$ və $b$ rəqəmlərinin cəmini qaytarır.

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

C++

$Z_{p} (c)$ Z_p (\sqrt{c}) sahəsində çıxma əməliyyatını reallaşdırırıq. sub funksiyası $a$ və $b$ rəqəmlərinin fərqini qaytarır.

Num sub(Num& a, Num& b)
{
  Num res;
  res.x = (a.x - b.x + p) % p;
  res.y = (a.y - b.y + p) % p;
  return res;
}

C++

$Z_{p} (c)$ Z_p (\sqrt{c}) sahəsində vurma əməliyyatını reallaşdırırıq. mult funksiyası $a$ və $b$ rəqəmlə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 dərəcəsinə yüksəltməni reallaşdırır, burada $ba se$ $Z_{p} (c)$ Z_p (\sqrt{c}) sahəsində olan rəqəmdir.

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

C++

divide funksiyası $Z_{p} (c)$ Z_p (\sqrt{c}) sahəsində bölməni reallaşdırır. O, $a$ və $b$ rəqəmlərinin bölünməsini qaytarır. Bölmə əks elementin vurulması ilə həyata keçirilir:

\frac{a}{b} = \frac{a _{x} + a _{y} c}{b _{x} + b _{y} c} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{( b _{x} + b _{y} c ) ( b _{x} - b _{y} c )} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{b _{x}^{2} - b _{y}^{2} c} = (a_{x} + a_{y} c) (b_{x} - b_{y} c) (b_{x}^{2} - b_{y}^{2} c)^{- 1}

Num divide(Num& a, Num& b)
{

Tutaq ki, $co nj = b_{x} - b_{y} c$ conj = b_x - b_y \sqrt{c}.

  Num conj = { b.x, (p - b.y) % p };

$n = (a_{x} + a_{y} c) (b_{x} - b_{y} c)$ n = (a_x + a_y \sqrt{c})(b_x - b_y \sqrt{c}) hesablayırıq.

  Num n = mult(a, conj);

$d e n o m = b_{x}^{2} - b_{y}^{2} c$ denom = b_x^2 - b_y^2 c hesablayırıq.

  long long denom = 
    ((b.x * b.x) % p - ((b.y * b.y) % p * c) % p + p) % p;

Əks elementi hesablayırıq və $n / d e n o m = n \cdot d e n o m^{- 1}$ n / denom = n \cdot denom^{-1} qaytarırıq.

  long long inv_denom = modpow(denom, p - 2, p); // əks element
  return Num((n.x * inv_denom) % p, (n.y * inv_denom) % p);
}

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

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

Rəqəmi $x = a + b c$ x = a + b \sqrt{c} və sahənin vahidini $o n e = 1 + 0 c$ one = 1 + 0 \sqrt{c} olaraq təyin edirik.

Num x = { a % p, b % p };
Num one = { 1, 0 };

$n u m = x^{n + 1} - 1$ num = x^{n+1} - 1, $d e n o m = x - 1$ denom = x - 1 hesablayırıq.

Num num = pow(x, n + 1);
num = sub(num, one);
Num denom = sub(x, one);

Cavabı $r es = n u m / d e n o m = \frac{x ^{n + 1} - 1}{x - 1}$ res = num / denom = \frac{x^{n+1} - 1}{x - 1} hesablayırıq və çap edirik.

Num res = divide(num, denom);
printf("%lld %lld\n", res.x, res.y);