快速乘用于两个ll整数乘法取模可能溢出的情况。
原理:ull溢出相当于对\(2^64\)次方取模
代码:
inline ll ksc(ll x,ll y,ll mod){
ll z=(ld)x/mod*y;
ll res=(ull)x*y-(ull)mod*z;
return (res%mod+mod)%mod;
}
2024-01-16 16:33:40
快速乘用于两个ll整数乘法取模可能溢出的情况。
原理:ull溢出相当于对\(2^64\)次方取模
代码:
inline ll ksc(ll x,ll y,ll mod){
ll z=(ld)x/mod*y;
ll res=(ull)x*y-(ull)mod*z;
return (res%mod+mod)%mod;
}