1083. Sequence

In a sequence of numbers a₁, a₂, a₃, ...  the first term is given, and the other terms are calculated using the formula:

a_i = (a_i-1 * a_i-1) mod 10000

Find the n-th term of the sequence.

Input. The first row contains the numbers a₁ and n (0 ≤ a₁ ≤ 10000, 1 ≤ n ≤ 2000000010).

Output. Print the value of a_n.

Sample input	Sample output
4 3	256

SOLUTION

exponentiation

Algorithm analysis

Let us express the first terms of the sequence in terms of a₁:

· a₂ = a₁² mod 10000,

· a₃ = a₂² mod 10000 = a₁⁴ mod 10000,

· a₄ = a₃² mod 10000 = a₂⁴ mod 10000 = a₁⁸ mod 10000

The formula can be rewritten as a_i = a_i-1² mod 10000, whence it follows that to calculate a_n, the number a₁ should be raised to the power 2^n–1:

Considering that a^b mod n = a^{b mod j(n)} mod n, to find the result res, the following calculations should be performed:

x = 2^n–1 mod j(10000) = 2^n–1 mod 4000,

res = a₁^x mod 10000

Algorithm realization

Function PowMod finds the value of xⁿ mod m.

int PowMod(int x, int n, int m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

Read the input data.

scanf("%d %d",&a,&n);

First find the value of x = 2^n–1 mod 4000, and then find and print the answer

res = a^x mod 10000

x = PowMod(2,n-1,4000);

res = PowMod(a,x,10000);

printf("%d\n",res);

Java realization

import java.util.*;

public class Main

{

static long PowMod(long x, long n, long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long a = con.nextLong();

long n = con.nextLong();

long x = PowMod(2,n-1,4000);

long res = PowMod(a,x,10000);

System.out.println(res);

con.close();

}

}