Sequence#1083

Sequence (Editorial)

Let us express the first terms of the sequence in terms of $a_{1}$ a_1:

$a_{2} = a_{1}^{2} m o d 10000$ a_2 = a_1^2~mod~10000,
$a_{3} = a_{2}^{2} m o d 10000 = a_{1}^{4} m o d 10000$ a_3 = a_2^2~mod~10000 = a_1^4~mod~10000,
$a_{4} = a_{3}^{2} m o d 10000 = a_{2}^{4} m o d 10000 = a_{1}^{8} m o d 10000$ a_4 = a_3^2~mod~10000 = a_2^4~mod~10000 = a_1^8~mod~10000

Thus, the formula can be written as:

a_{i} = a_{i - 1}^{2} m o d 10000

a_i = a_{i-1}^2~mod~10000

Which means that to compute $a_{n}$ a_n, it is enough to raise $a_{1}$ a_1 to the power of $2^{n - 1}$ 2^{n - 1} modulo $10000$ :

a_{n} = a_{1}^{2^{n - 1}} m o d 10000

a_n = a_1^{2^{n-1}}~mod~10000

Taking into account the modular exponentiation identity:

a^{b} m o d n = a^{b m o d ϕ (n)} m o d n,

a^b~mod~n = a^{b~mod~\phi(n)}~mod~n,

we proceed as follows to find the result $r es$ :

Compute $x = 2^{n - 1} m o d ϕ (10000) = 2^{n - 1} m o d 4000$ x = 2^{n - 1}~mod~ \phi (10000) = 2^{n - 1}~mod~4000,
Then compute $r es = a_{1}^{x} m o d 10000$ res = a_1^x~mod~10000

Algorithm implementation

The function PowMod computes the value of $x^{n} m o d m$ x^n~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);

Compute $x = 2^{n - 1} m o d 4000$ x = 2^{n - 1}~mod~4000. And after that, compute and print the final answer:

r es = a^{x} m o d 10000

res = a^x~mod~10000

x = PowMod(2,n-1,4000);
res = PowMod(a,x,10000);
printf("%d\n",res);

Java implementation

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

Java