Послідовність#1083

Послідовність (Розбір)

Виразимо перші члени послідовності через $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

Таким чином, формулу можна записати у вигляді:

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

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

Звідки випливає, що для обчислення $a_{n}$ a_n достатньо піднести $a_{1}$ a_1 до степеня $2^{n - 1}$ 2^{n - 1} за модулем $10000$ :

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

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

Враховуючи, що

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,

для отримання результату $r es$ слід виконати такі обчислення:

Обчислити значення $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,
Потім обчислити $r es = a_{1}^{x} m o d 10000$ res = a_1^x~mod~10000

Реалізація алгоритму

Функція PowMod обчислює значення $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;
}

Читаємо вхідні дані.

scanf("%d %d",\u0026a,\u0026n);

Обчислюємо $x = 2^{n - 1} m o d 4000$ x = 2^{n - 1}~mod~4000. Після чого знаходимо та виводимо відповідь:

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 реалізація

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