Define the infinite
sequence A as follows:
A0 = 1,
Ai = A[i/p]
+ A[i/q] , i ³ 1
Given n, p and q, compute the value of An.
Input. Three integers n, p and q (0 £ n £ 1012, 2 £ p, q £ 109).
Output. Print the value of An.
|
Sample
input 1 |
Sample
output 1 |
|
0 2 3 |
1 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
10000000 3 3 |
32768 |
SOLUTION
data
structures – map, recursion
Algorithm analysis
Calculating all values of Ai for i = 0, 1, …, n
using an array is impossible due to the constraint n ≤ 10¹². To store
the computed results, use a map data structure: the value of Ai will be stored in m[i]. Ñompute An by memorizing intermediate
results.
Algorithm implementation
To store the values of Ai, 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));
}
}