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

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

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

При цьому значення $A_{i}$ A_i для яких $i < 5000000$ i < 5000000, будемо зберігати в масиві $m$ , щоб уникнути повторних обчислень і прискорити виконання програми.

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

Для зберігання значень $A_{i} (i < 5000000)$ A_i~(i < 5000000) оголосимо масив $m$ .

#define MAX 5000000
long long m[MAX];

Функція f обчислює значення $A_{n}$ A_n.

long long f(long long n, long long p, long long q, 
            long long x, long long y)
{

Якщо $n \leq 0$ n \le 0, то $A_{n} = 1$ A_n = 1.

  if (n <= 0) return 1;

Якщо $n < 5000000$ n < 5000000 і значення $m [n]$ вже обчислено (відмінно від нуля), то повертаємо його.

  if ((n < MAX) && m[n]) return m[n];

Виконуємо рекурсивне обчислення значення $A_{n}$ A_n відповідно до формули, наведеної в умові задачі.

  long long temp = f(n/p-x,p,q,x,y) + f(n/q-y,p,q,x,y);

Якщо $n < 5000000$ n < 5000000, зберігаємо результат $A_{n}$ A_n в масиві $m$ , щоб уникнути повторних обчислень в майбутньому.

  if (n < MAX) m[n] = temp;
  return temp;
}

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

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

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

res = f(n,p,q,x,y);
printf("%lld\n",res);

Java реалізація

import java.util.*;

public class Main
{
  static int MAX = 5000000;
  static long m[] = new long[MAX];
  
  public static long f(long n, long p, long q, long x, long y)
  {
    if (n <= 0) return 1;	  
    if (n < MAX && m[(int)n] > 0) return m[(int)n];
    
    long temp = f(n/p-x,p,q,x,y) + f(n/q-y,p,q,x,y);
    if (n < MAX) m[(int)n] = temp;

    return temp;    
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    
    long n = con.nextLong();
    long p = con.nextLong();
    long q = con.nextLong();
    long x = con.nextLong();
    long y = con.nextLong();
    
    long res = f(n,p,q,x,y);
    System.out.println(res);
    con.close();
  }
}

Java

Python реалізація

Для зберігання значень $A_{i} (i < 5000000)$ A_i~(i < 5000000) оголосимо список $m$ .

MAX = 5000000
m = [0] * MAX