Ardıcıllıq#1083

Ardıcıllıq (Həll təhlili)

Ardıcıllığın ilk hədlərini $a_{1}$ a_1 vasitəsilə ifadə edək:

$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

Beləliklə, düsturu aşağıdakı şəkildə yazmaq olar:

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

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

Buradan belə nəticə çıxır ki, $a_{n}$ a_n-i hesablamaq üçün $a_{1}$ a_1-i $2^{n - 1}$ 2^{n - 1} dərəcəsinə $10000$ modulu ilə qaldırmaq kifayətdir:

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

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

Nəzərə alsaq ki,

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$ nəticəsini əldə etmək üçün aşağıdakı hesablamaları yerinə yetirmək lazımdır:

$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 qiymətini hesablamaq,
Sonra $r es = a_{1}^{x} m o d 10000$ res = a_1^x~mod~10000 hesablamaq

Alqoritmin realizasiyası

PowMod funksiyası $x^{n} m o d m$ x^n~mod~m qiymətini hesablayır.

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

Giriş məlumatlarını oxuyuruq.

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

$x = 2^{n - 1} m o d 4000$ x = 2^{n - 1}~mod~4000 hesablayırıq. Bundan sonra cavabı tapıb çap edirik:

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 realizasiyası

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