190326 BOJ 1354번 무한 수열 2

메모이제이션

- 조건이 추가된 것 외에는 1351번 무한 수열과 풀이와 같다.

소스 코드

#include <iostream>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define ll long long
using namespace std;
ll N, P, Q, X, Y;
ll D[1000000];
ll solve(ll n) {
    ll x = n / P - X, y = n / Q - Y;
    if (n == 1) return 2;
    else if (n <= 0) return 1;
    if (n < 1000000 && n >= 0) {
        if (D[n] != 0) return D[n];
        return D[n] = solve(x) + solve(y);
    }
    return solve(x) + solve(y);
}
int main() {
    D[0] = 1, D[1] = 2;
    cin >> N >> P >> Q >> X >> Y;
    cout << solve(N);
}