карта (long long int, long long int) не работает для ключа = 1000 000 000 (в диапазоне long long int)

Question

Недавно я задал вопрос, но о рекурсии, которая порождает эту проблему

Примечание-> count () Функция возвращает количество раз, когда ключ K присутствует в контейнере карты. Возвращает 1, если ключ присутствует в контейнере, поскольку карта содержит только уникальный ключ. Возвращает 0, если ключ отсутствует в контейнере карты. Он проходит почти все тестовые случаи, но не проходит 1 000 000 000 в соответствии с длинным длинным значением int, он также должен пройти этот, но это какое-то отрицательное значение в качестве выхода; Я думаю, что это проблема с картой контейнера Кто-нибудь может мне помочь, что не так с картой?

    #include<bits/stdc++.h>
    using namespace std;
    map <long long int,long long int> dp;
    int exchange(long long int n){
        if(n<12)
            return n;
        if(dp.count(n))
            return dp[n];
        return dp[n] = exchange(n/2)+exchange(n/3)+exchange(n/4);
    }
    int main(){
     //   int t;
       // cin>>t;
        while(1){
      //      memset(dp,-1,sizeof(dp));
            long long int n;
            cin>>n;
            cout<<exchange(n)<<endl;
        }

    }

Answer 1

Во-первых, это плохо: #include<bits/stdc++.h> Если вам нужна карта, используйте:

#include <map>

Тогда, что касается типов, если вам нужно что-то, что хранило более 2 миллиардов, используйте тип, который вы можете убедиться, что можете его хранить (особенно для возвращаемого типа!):

#include <iostream>
#include <map>

int64_t exchange(std::map& <int64_t, int64_t>, int64_t n){
    if(n<12)
        return n;
    if(dp.count(n))
        return dp[n];
    return dp[n] = exchange(n/2)+exchange(n/3)+exchange(n/4);
}
int main(){
    std::map <int64_t, int64_t> dp;
    while(1){
        int64_t n;
        std::cin>>n;
        std::cout<<exchange(dp, n)<<std::endl;
    }

}

Answer 2

Проблема в вашей функции exchange - она ​​возвращает int, что является более узким типом, чем long long int.