Infinite Sequence

Interview

Time limit2sMemory limit128 MB

Summary
Compute the N-th term of a sequence where A_i equals A at floor(i/P) plus A at floor(i/Q), using memoized recursion for huge N.
Level

Medium4 of 10

Topics
Recursion, Dynamic programming, Hash map, Math
Solved
No attempts yet

Problem

An infinite sequence A is defined as follows.

  • A_0 = 1
  • For i ≥ 1, A_i = A_⌊i / P⌋ + A_⌊i / Q⌋

Given integers N, P, and Q, write a program that computes A_N.

Input

The first line contains three integers N, P, and Q separated by spaces.

Output

Print the value of A_N.

Constraints

  • 0 ≤ N ≤ 10^12
  • 2 ≤ P, Q ≤ 10^9

Hint

⌊x⌋ is the greatest integer that is not greater than x.

Examples5

  1. Example 1

    Input
    7 2 3
    Expected output
    7

  2. Example 2

    Input
    0 2 3
    Expected output
    1

  3. Example 3

    Input
    10000000 3 3
    Expected output
    32768

  4. Example 4

    Input
    256 2 4
    Expected output
    89

  5. Example 5

    Input
    1 1000000 1000000
    Expected output
    2