c++ - 使用模运算的正确方法

Question

在一次编程竞赛中，我被要求用 1000000007 取模。

下面的代码显示了我是如何尝试实现它的。

#include <stdio.h>
#define ll long long
#define MOD 1000000007
ll getmin(ll a, ll b){return (a<b)?a:b;}

void solve(){
    ll a,b,c,Tv;
    scanf("%lld %lld %lld",&a,&b,&c);
    Tv = ((a%MOD)*(b%MOD)*(c%MOD))%MOD;
    ll sideofcube = getmin(a,getmin(b,c));
    ll numofcube = 0;
    ll smallvol = ((sideofcube%MOD)*(sideofcube%MOD)*(sideofcube%MOD))%MOD;
    numofcube = Tv/smallvol;
    printf("%lld %lld\n",sideofcube,numofcube);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

有输入

1
1000000000 1000000000 100000000

我得到了否定的回应

100000000 -1

这里出了什么问题？我什至在乘法之前就服用了 MOD。

Answer 1

((a%MOD)*(b%MOD)*(c%MOD)) 的乘积可以溢出 64 位整数。为避免此问题，一次只乘以两项:

    Tv = ((a % MOD) * (b % MOD)) % MOD;
    Tv = ((Tv) * (c % MOD)) % MOD;

此外，您应该为 ll 使用 typedef:

typedef long long ll;

在这种情况下，两项的乘积只需要 60 位 (log2(1000000007*1000000007))，因此乘积不会溢出变成负数。您可能希望使用 64 位无符号整数(ull 或 uint64_t)，因为它在某些系统上可能更快。