64位整数乘法

描述

求 a 乘 b 对 p 取模的值，其中 1≤a,b,p≤10^18。

输入格式

第一行a，第二行b，第三行p。

输出格式

一个整数，表示a*b mod p的值。

样例输入

2
3
9

样例输出

6

题解：类似于快速幂的思想，我们把b用二进制表示，即b=c^k-1*2^k-1+ck-2*2^k-2+...c0*2^0，那么a*b=ck-1*a*2^k-1+....c0*a*2^0。因为a*2^i=(a*2^i-1)*2,若已求出a*2^i-1 mod p，则计算（a*2^i-1）* 2 mod p 时，运算过程中每一步的结果都不会超过2*10^18，仍然在 long long 表示的范围内。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int maxn=100010;
LL mul(LL a, LL b, LL p){
LL ans=0;
while(b){
if(b&1) ans=(ans+a)%p;
a=a*2%p;
b>>=1;
}
return ans%p;
}
int main()
{
LL a,b,p;
cin>>a;
cin>>b;
cin>>p;
LL ans=mul(a,b,p);
cout<<ans<<endl;
return 0;
}

另一种解法：

利用 a*b mod p = a*b - (a*b/p)*p;

LL mul(LL a, LL b, LL p){
a%=p,b%=p;//当a,b一定在0~p之间时，此行不必要
LL c = (long double)a*b/p;
LL ans=a*b-c*p;
if(ans<0) ans+=p;
else if(ans>=p) ans-=p;
return ans;
}

最后

以上就是彪壮人生为你收集整理的64位整数乘法的全部内容，希望文章能够帮你解决64位整数乘法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。