AcWing 90. 64位整数乘法
原题链接
简单
作者:
Karma
,
2019-11-02 14:41:33
,
所有人可见
,
阅读 729
利用公式 $a * b$ mod $p=a * b-\lfloor a * b / p\rfloor * p$
#include <iostream>
using namespace std;
typedef long long LL;
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
LL a, b, p;
cin >> a >> b >> p;
if(p == 1)
{
cout << 0 << endl;
}
else
{
// 利用公式 $a * b$ mod $p=a * b-\lfloor a * b / p\rfloor * p$
// 后面的 a*b/p 转换为 long double(有效精度 18~19 位)并向下取整是为了保存较高位,
// *p 后可能越界,不精确,但前后相减不影响最后结果。
// 转换为long double,舍弃低位
LL tmp = (long double)a * b / p;
// 此时前后均可能溢出,但相减后无影响
LL res = a * b - tmp * p;
// 书上认为res可能为负数,对负数进行了讨论(未理解)
// 此处暂时这么写。
res = res % p;
cout << res << endl;
}
}