在一次编程竞赛中,我被要求用 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。
最佳答案
((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
),因为它在某些系统上可能更快。
关于c++ - 使用模运算的正确方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43571245/