Consider an infinite
sequence A defined as follows:
A0 = 1,
Ai = A[i/p]
+ A[i/q] , i ³ 1
You will be given n, p
and q. Find the value of An.
Input. Three integers n, p and q (0 £ n £ 1012, 2 £ p, q £ 109).
Output. 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
To calculate all the
values of the sequence Ai
(i = 0, 1, …, n) using an array is impossible because of the restriction n £ 1012. To memoize the results, we shall use a map structure: the value of Ai will be stored in m[i]. Calculate the values of An memoizing the intermediate
results.
Algorithm realization
To store the values of Ai declare the variable m.
map<long long,long long> m;
The function calc returns the value of 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. Compute and print the
answer.
scanf("%lld
%lld %lld",&n,&p,&q);
res = calc(n,p,q);
printf("%lld\n",res);
Java realization
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));
}
}