An Ordinary Sequence [yukicoder No.639]

https://yukicoder.me/problems/no/639

解法

https://yukicoder.me/submissions/232176

メモ化再帰すると通る。
なぜ通るかは分からないけど、÷3,÷5されているので状態そんなになさそうな感じがある。

map<ll, ll> memo;
//---------------------------------------------------------------------------------------------------
ll f(ll x) {
    if (x == 0) return 1;
    if (memo.count(x)) return memo[x];
    return memo[x] = f(x / 3) + f(x / 5);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    ll N; cin >> N;
    cout << f(N) << endl;
}