Sonsuz ardıcıllıq - 2#1212

Sonsuz ardıcıllıq - 2 (Həll təhlili)

Çünki $n \leq 1 0^{13}$ n \le 10^{13}, $A_{i} (i = 0, 1, ..., n)$ A_i~(i = 0, 1, ..., n) bütün dəyərlərini yadda saxlamaq nə massiv, nə də map strukturu ilə mümkündür, çünki yaddaş məhdudiyyətləri var. Buna görə də, hesablamalar üçün rekursiyadan istifadə edəcəyik, verilmiş rekursiya tənliyi ilə.

Bununla belə $A_{i}$ A_i dəyərləri üçün $i < 5000000$ i < 5000000, bu dəyərləri massiv $m$ -də saxlayacağıq ki, təkrar hesablamalardan qaçaraq proqramın icrasını sürətləndirək.

Alqoritmin realizasiyası

$A_{i} (i < 5000000)$ A_i~(i < 5000000) dəyərlərini saxlamaq üçün massiv $m$ elan edirik.

#define MAX 5000000
long long m[MAX];

f funksiyası $A_{n}$ A_n dəyərini hesablayır.

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

Əgər $n \leq 0$ n \le 0, onda $A_{n} = 1$ A_n = 1.

  if (n <= 0) return 1;

Əgər $n < 5000000$ n < 5000000 və $m [n]$ dəyəri artıq hesablanıbsa (sıfırdan fərqlidirsə), onu qaytarırıq.

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

Verilmiş məsələnin şərtindəki formulaya uyğun olaraq $A_{n}$ A_n dəyərinin rekursiv hesablanmasını yerinə yetiririk.

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

Əgər $n < 5000000$ n < 5000000, əldə edilən $A_{n}$ A_n nəticəsini massiv $m$ -də saxlayırıq ki, gələcəkdə təkrar hesablamalardan çəkinək.

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

Proqramın əsas hissəsi. Giriş məlumatını oxuyuruq.

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

Hesablayır və cavabı çıxardırıq.

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

Java həyata keçirilməsi

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 həyata keçirilməsi

$A_{i} (i < 5000000)$ A_i~(i < 5000000) dəyərlərini saxlamaq üçün siyahı $m$ elan edirik.

MAX = 5000000
m = [0] * MAX