Разбор

Для запоминания результатов значений функции $f$ из-за ограничения $n \leq 1 0^{18}$ невозможно использовать линейный массив. Поэтому будем использовать структуру данных map.

Пример

Рассмотрим процесс вычисления функции для $n = 5$ :

Реализация алгоритма

Объявим отображение $m$ для хранения значений функции: $m [n] = f (n)$ .

map<long long, long long> m;

Реализация функции f.

long long f(long long n)
{
  if (n == 0) return 1;
  if (m.count(n) > 0) return m[n];
  return m[n] = f(n / 2) + f(n / 3);
}

Основная часть программы. Читаем входное значение $n$ . Вычисляем и выводим значение функции $f (n)$ .

scanf("%lld", &n);
res = f(n);
printf("%lld\n", res);

Java реализация

import java.util.*;

public class Main
{
  static Map<Long, Long> m = new HashMap<Long, Long>();
  static long n;
  
  public static long f(long n)
  {
    if (n == 0) return 1;
    if (m.containsKey(n)) return m.get(n);
    long res = f(n/2) + f(n/3);
    m.put(n,res);
    return res;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextLong(); 
    System.out.println(f(n));
    con.close();
  }
}

Python реализация

Объявим словарь $m$ для хранения значений функции: $m [n] = f (n)$ .

m = {}

Реализация функции f.

def f(n):
  if n == 0:
    return 1
  if n in m:
    return m[n]
  m[n] = f(n // 2) + f(n // 3)
  return m[n]

Основная часть программы. Читаем входное значение $n$ . Вычисляем и выводим значение функции $f (n)$ .

n = int(input())
res = f(n)
print(res)