Задача 5923. Источник: Поляков. Задание КИМ 16
(Е. Джобс) Алгоритм вычисления функции F(n), где n – неотрицательное число, задан следующими соотношениями:
F(1) = 2,
F(n) = F(n-1)·3n % 5 / 3n % 7
Чему равно значение выражения F(1025) / F(1030)? В ответе запишите только целое число. Примечание: операция a % b находит остаток от деления числа a на число b.
Решение
В данной задаче нет смысла вычислять значения элементов, т.к. с некоторого элемента значение станет настолько маленьким, что будет приравнено к нулю. В качестве результата будем вычислять степень тройки, которую и используем для вычисления ответа.
Python
f = [0] * 1031
for n in range(2, 1031):
f[n] = f[n - 1] + n % 5 - n % 7
print(3 ** (f[1025] - f[1030]))
PascalABC
var
n: Integer;
f: array[1..1030] of Integer;
begin
f[1] := 0;
for n := 2 to 1030 do
f[n] := f[n - 1] + n mod 5 - n mod 7;
Writeln(trunc(power(3, f[1025] - f[1030])));
end.
C++
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int f[1031];
f[1] = 0;
for (int n = 2; n < 1031; n++)
f[n] = f[n - 1] + n % 5 - n % 7;
cout << (int)pow(3, f[1025] - f[1030]);
}
Ответ
729