1083. Последовательность
В последовательности чисел a1, a2,
a3, ... задан первый член,
а остальные вычисляются по формуле:
ai = (ai-1
* ai-1) mod
10000
Найти n-ый член
последовательности.
Вход. В первой строке находятся числа a1 и n (0 ≤ a1
≤ 10000, 1 ≤ n ≤
2000000010).
Выход. Вывести
одно число an.
|
Пример входа |
Пример выхода |
|
4 3 |
256 |
РЕШЕНИЕ
возведение
в степень
Анализ алгоритма
Выразим первые
члены последовательности через a1:
·
a2 =
a12 mod 10000,
·
a3 =
a22 mod 10000 =
a14 mod 10000,
·
a4 =
a32 mod 10000 =
a24 mod 10000 =
a18 mod 10000
Формулу можно
переписать в виде ai = ai-12
mod 10000, откуда следует что для вычисления an число a1 следует возвести в степень 2n–1 :
Учитывая что ab mod n
= ab mod j(n) mod n, то для нахождения результата res следует произвести следующие вычисления:
x = 2n–1 mod j(10000) =
2n–1 mod 4000,
res = a1x mod 10000
Реализация
алгоритма
Функция PowMod вычисляет
значение xn 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",&a,&n);
Вычисляем x = 2n–1 mod 4000, после чего находим и выводим ответ
res = ax 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();
}
}