12318. Sum in field

 

For the given integers a, b, c, n, p, compute the value of the sum:

Print the result as two numbers x and y such that

Input. Five integers a, b, c, n, p. It is known that:

·        p < 109  is a prime number,

·        0 ≤ a, b < p,

·        1 ≤ c < p,

·        0 ≤ n ≤ 109

 

Output. Print two integers x and y – the coefficients of 1 and  respectively, modulo p.

 

Sample input 1

Sample output 1

2 1 5 2 17

12 5

 

 

Sample input 2

Sample output 2

3 2 5 10 17

15 6

 

 

SOLUTION

combinatorics

 

Algorithm analysis

All computations should be performed in the extended field:

Operation rules:

·        Addition

·        Multiplication

 

Let x = . Then the required sum is a finite geometric progression:

1 + x + x2 + x3 + … + xn =  =

It remains to perform the division a = xn+1 – 1 by b = x – 1 in the field :

=  =  =  =

 

Example

In the first example

 =

(1 + () + ()) mod 17 =  12

Let’s compute this example using the formula:

 =  =

=  =  =  =

 =  =  =  =

 =  =

 

In the second example

 = 15

 

Algorithm implementation

The function modpow computes the value ak 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;

}

 

Let’s define a structure Num to store numbers of the form .

 

struct Num

{

  long long x, y; // x + y*sqrt(c)

};

 

Let’s implement addition in the field . 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;

}

 

Let’s implement subtraction in the field . 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;

}

 

Let’s implement multiplication in the field . 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 of basen, where base is an element of the field .

 

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 function divide implements division in the field . It returns the quotient of the numbers a and b. The division is performed by multiplying by the conjugate:

=  =  =  =

 

Num divide(Num& a, Num& b)

{

 

Let conj = .

 

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

 

Compute n = .

 

  Num n = mult(a, conj);

 

Compute denom = .

 

  long long denom =

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

 

Compute the multiplicative inverse and return n / denom = n * 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 =  and the multiplicative identity of the field one = .

 

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

Num one = { 1, 0 };

 

Compute num = xn+1 – 1, denom = x – 1.

 

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

num = sub(num, one);

Num denom = sub(x, one);

 

Compute and print the answer res = num / denom = .

 

Num res = divide(num, denom);

printf("%lld %lld\n", res.x, res.y);