Sum in field#12318

Sum in field (Editorial)

All computations should be performed in the extended field:

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

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

Operation rules:

Addition

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

Multiplication

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

Let $x = a + b c$ x = a + b \sqrt{c}. Then the required sum is a finite geometric progression:

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}

It remains to perform the division $a = x^{n + 1} - 1$ a = x^{n + 1} - 1 by $b = x - 1$ b = x - 1 in the field $Z_{p} (c)$ Z_p (\sqrt{c}):

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

Example

In the first example

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}

Let's compute this example using the formula:

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}

In the second example

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}

Algorithm implementation

The function modpow computes the value $a^{k} m o d p$ a^k~mod~p.

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++

Let's define a structure $N u m$ to store numbers of the form $x + y c$ x + y \sqrt{c}.

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

Let's implement addition in the field $Z_{p} (c)$ Z_p (\sqrt{c}). The function add returns the sum of two numbers $a$ and $b$ .

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++

Let's implement subtraction in the field $Z_{p} (c)$ Z_p (\sqrt{c}). The function sub returns the difference of two numbers $a$ and $b$ .

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++

Let's implement multiplication in the field $Z_{p} (c)$ Z_p (\sqrt{c}). The function mult returns the product of two numbers $a$ and $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++

The function pow implements exponentiation of $ba s e^{n}$ base^n, where $ba se$ is an element of the field $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++

The function divide implements division in the field $Z_{p} (c)$ Z_p (\sqrt{c}). It returns the quotient of the numbers $a$ and $b$ . The division is performed by multiplying by the conjugate:

\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)
{

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

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

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

  Num n = mult(a, conj);

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

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

Compute the multiplicative inverse and return $n / d e n o m = n \cdot d e n o m^{- 1}$ n / denom = n \cdot denom^{-1}.

  long long inv_denom = modpow(denom, p - 2, p); // обратный элемент
  return Num((n.x * inv_denom) % p, (n.y * inv_denom) % p);
}

The main part of the program. Read the input data.

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

Initialize the number $x = a + b c$ x = a + b \sqrt{c} and the multiplicative identity of the field $o n e = 1 + 0 c$ one = 1 + 0 \sqrt{c}.

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

Compute $n u m = x^{n + 1} - 1$ num = x^{n+1} - 1, $d e n o m = x - 1$ denom = x - 1.

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

Compute and print the answer $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}.

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