Infinite Sequence#1211

Infinite Sequence (Editorial)

Calculating all values of $A_{i}$ A_i for $i = 0, 1, ..., n$ i = 0, 1, ..., n using an array is impossible due to the constraint $n \leq 1 0^{12}$ n \le 10^{12}. To store the computed results, use a map data structure: the value of $A_{i}$ A_i will be stored in $m [i]$ . Сompute $A_{n}$ A_n by memorizing intermediate results.

Algorithm implementation

To store the values of $A_{i}$ A_i, declare the variable $m$ .

map<long long,long long> m;

The function calc returns the value $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);
}

The main part of the program. Read the input data.

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

Compute and print the answer.

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

Java implementation

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