Untitled
unknown
plain_text
2 months ago
817 B
1
Indexable
#include <bits/stdc++.h> using namespace std; // We'll memoize f(n) in a hash map to avoid recomputing. unordered_map<long long, long long> memo; // Define the function f(n) recursively with memoization. long long f(long long n) { // Base case: if (n == 0) { return 1; } // If we already computed f(n), return it from the memo table. if (memo.count(n)) { return memo[n]; } // Recurrence: f(n) = f(n/2) + f(n/3) for n > 0. long long result = f(n / 2) + f(n / 3); // Store in memo before returning. memo[n] = result; return result; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n; cin >> n; // Read the (potentially large) input cout << f(n) << "\n"; return 0; }
Editor is loading...
Leave a Comment