1351

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class BOJ1351 {

    static Map<Long,Long> map;
    static int p;
    static int q;

    static long answer(long num){

        // 초항 : a의 0번째는 1
        if(num == 0) return 1;
        // 만약 map이 num 키를 가지면 값 리턴
        if(map.containsKey(num)) return map.get(num);

        // ⌊x⌋는 x를 넘지 않는 가장 큰 정수이므로 버림(floor)처리해줌
        long first = (long) Math.floor(num/p);
        long second = (long) Math.floor(num/q);

        map.put(num, answer(first) + answer(second));

        return map.get(num);

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr = br.readLine().split(" ");
        int[] numArr = Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();

        int n = numArr[0];
        p = numArr[1];
        q = numArr[2];

        map = new HashMap<>();

        System.out.println(answer(n));
    }
}

https://www.acmicpc.net/problem/1351