Условие задачи
Вычислите функцию:
$$f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}$$
Входные данные
Одно натуральное число $n$ $(1 \leq n \leq 10^{12})$
Выходные данные
Значение $f(n)$ , взятое по модулю $2^{32}$.
Тесты
| Входные данные | Выходные данные |
|---|---|
10 |
7 |
123 |
229966 |
1 |
1 |
100 |
136345 |
51 |
5092 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Map; import java.util.HashMap; import java.lang.Math; class Main { private static long mod = 1L << 32; public static Map<Long, Long> mp = new HashMap<Long, Long>(); public static long f(long n) { if (n <= 2) { return 1; } if (mp.containsKey(n)) { return mp.get(n); } if (n % 2 == 1) { long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod; mp.put(n, d); return mp.get(n); } long o = (f(n - 1) % mod + f(n - 3) % mod) % mod; mp.put(n, o); return mp.get(n); } public static void main (String[] args) throws java.lang.Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params1 = bufferedReader.readLine().split(" "); long n; n = Long.parseLong(params1[0]); System.out.print(f(n)); } } |
Решение задачи
Решение данной задачи стоит начать с написания рекурсивной функции для вычисления функций по условию задачи. Так как рекурсия будет довольно таки сложной и много раз повторяются одни и те же результаты при вызове функции, следовательно, программа будет долгое время обрабатывать нашу задачу. То есть, к примеру, на 5 и 20 итерации, возвращаемые значения функции могут совпасть, что без оптимизации будет просчитываться еще раз, а с оптимизацией функция уже знает, чему равно значение с данными аргументами.Далее, по условию, мы пишем наконец нашу функцию:
- Если число, которое ввел пользователь, меньше либо равно двум, то наша функция возвращает значение один.
- Если есть значение с таким же ключом, то оно возвращает значение.
- Если число, которое ввел пользователь, дает остаток от деления один, то наша функция возвращает значение $f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor)$.
- Во всех остальных случаях наша функция возвращает значение $f(n-1)+f(n-3)$.