值达到 pow(10,19) 的整数溢出

Question

这是我遇到溢出问题的代码。

我的问题中指定的约束是(0 ≤ v, c, n, m ≤ pow(10,18))

此测试用例我的代码失败：63434583954291753 66777666160449180 94688604155374928 61081164840594246

P.S。执行我的代码没有问题。只是想避免溢出。 :).我尝试使用 mod=pow(10,19)+7 和 unsigned long long 来避免溢出。仍然；它不起作用。

#include<iostream>
#include<cmath>
using namespace std;

bool helper(unsigned long long int v,unsigned long long int c,unsigned long long int n,unsigned long long int m,int **output){
    if(n==0 && m==0)
        return true;
    if(n==0){
        if(v > c){
            if(m <= c)
                return true;
            else
                return false;
        }
        else{
            if(m <= v){
                return true;
            }else
                return false;
        }
    }
    if(m==0){
        if(v > c){
            if(n <= v)
                return true;
            else
                return false;
        }
        else{
            if(n <= c){
                return true;
            }else
                return false;
        }
    }
    if(output[n][m]!= -1)
        return output[n][m];
    bool choice1=false;
    bool choice2=false;
    if(v > c){
        if(v>=1)
            choice1=helper(v-1,c,n-1,m,output);
        else
            choice1=false;
    }
    else{
        if(c>=1)
            choice1=helper(v,c-1,n-1,m,output);
        else
            choice1=false;
    }
    if(v > c){
        if(c>=1)
            choice2=helper(v,c-1,n,m-1,output);
        else
            choice2=false;
    }
    else{
        if(v>=1)
            choice2=helper(v-1,c,n,m-1,output);
        else
            choice2=false;
    }
    bool ans=choice1||choice2;
    if(ans)
        output[n][m]=1;
    else
        output[n][m]=0;
    return output[n][m];
}

int main(){
    int t;cin>>t;
    unsigned long long int mod=pow(10,19)+9;
    while(t--){
        unsigned long long int v,c,n,m;
        cin>>v>>c>>n>>m;
        int **output=new int*[(n+1)%mod];
        for(unsigned long long int i=0;i<(n+1)%mod;i++){
            output[i]=new int[(m+1)%mod];
            for(unsigned long long int j=0;j<(m+1)%mod;j++)
                output[i][j]= -1;
        }
        bool ans=helper(v%mod,c%mod,n%mod,m%mod,output);
        if(ans==1)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}

Answer 1

您输入的 n = 94,688,604,155,374,928。然后在行

int **output=new int*[(n+1)%mod]

这意味着你要求系统分配n个整数指针的内存。假设您的操作系统是 64 位，这大约是 90,000 * 8 TB 内存。我怀疑你的电脑有那么多 RAM。

使用较小的数字，不要使用这些非常大的值。

值达到 pow(10,19) 的整数溢出

Integer-Overflow for values upto pow(10,19)

c++

constraints

integer-overflow

c++11