Sequenza#1083

Sequenza (Editoriale)

Esprimiamo i primi termini della successione in funzione di $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

In questo modo, la formula può essere scritta nella forma:

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

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

Da cui segue che per calcolare $a_{n}$ a_n è sufficiente elevare $a_{1}$ a_1 alla potenza $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

Tenendo conto che

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,

per ottenere il risultato $r es$ occorre eseguire i seguenti calcoli:

Calcolare il valore $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,
Quindi calcolare $r es = a_{1}^{x} m o d 10000$ res = a_1^x~mod~10000

Implementazione dell'algoritmo

La funzione PowMod calcola il valore $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;
}

Leggiamo i dati in input.

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

Calcoliamo $x = 2^{n - 1} m o d 4000$ x = 2^{n - 1}~mod~4000. Dopodiché troviamo e stampiamo la risposta:

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

Implementazione in 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