Field modulo (Editorial)

The number \sqrt{c} is irrational, so evaluating the expression in real numbers makes no sense: with $n$ up to 10^{18} it is impossible in terms of precision. Note, however, that any integer power of a + b\sqrt{c} again has the form x + y\sqrt{c}, since \sqrt{c} \cdot \sqrt{c} = c. Therefore, the computations should be performed in the extension field:

Operation rules:

• Addition

• Multiplication

After defining the multiplication operation, elements of the field Z_p (\sqrt{c}) can be raised to a power using the standard binary exponentiation method in O(log_2n) time. This makes it possible to compute (a + b \sqrt{c})^n~mod~p.

Example

In the first example

Let us consider the second example:

Let x = 3 + 2 \sqrt{5}. We'll compute its powers step by step:

Now we can compute the result:

Algorithm implementation

Let us define a structure $Num$ to store numbers of the form x + y \sqrt{c}.

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

Let's implement multiplication in the field 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;
}

The function pow implements exponentiation, computing base^n, where $base$ is a number in the field 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;
}

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

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

Initialize the starting number start = a + b \sqrt{c}.

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

Compute and print the answer 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);