Нескінченна послідовність#1211

Нескінченна послідовність (Розбір)

Обчислити всі значення $A_{i} (i = 0, 1, ..., n)$ A_i~(i = 0, 1, ..., n) неможливо за допомогою масиву через обмеження $n \leq 1 0^{12}$ n \le 10^{12}. Для запам'ятовування результатів будемо використовувати структуру даних map: значення $A_{i}$ A_i будемо зберігати в $m [i]$ . Значення $A_{n}$ A_n обчислюємо, запам'ятовуючи проміжні результати.

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

Для зберігання значень $A_{i}$ A_i оголосимо змінну $m$ .

map<long long,long long> m;

Функція calc повертає значення $m [n]$ .

long long calc(long long n, int p, int q)
{
  if (n == 0) return 1;
  if (m.count(n) > 0) return m[n];
  return m[n] = calc(n/p,p,q) + calc(n/q,p,q);
}

Основна частина програми. Читаємо вхідні дані.

scanf("%lld %lld %lld",&n,&p,&q);

Обчислюємо і виводимо відповідь.

res = calc(n,p,q);
printf("%lld\n",res);

Реалізація на Java

import java.util.*;

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

Java