题解 | 《算法竞赛进阶指南》64位整数乘法

【题目】

求 a 乘 b 对 p 取模的值，其中 $1\le a,b,p\le 10^{18}$

【题解】

普通的$a\times b$，在这个数据范围肯定是超出的，就算可以取余，但最坏的情况下，精度还是会溢出，在这种情况下我们就会想到快速幂。做法跟快速幂差不多，也是使用类似的反复翻倍法，即$2\times 5=4\times 2+2$，$3\times 5=6\times 2+3$,时间复杂度为$O(logN)$，网上很戏谑的称这种做法是龟速乘，跟快速幂成鲜明对比。听说还有一种是$O(1)$的做法，有兴趣的可以去百度查找一下。

时间复杂度：$O(logN)$

#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define lc (p<<1)
#define rc (p<<1|1)	
#define MID (tree[p].l+tree[p].r)>>1
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%dn",x)
#define Prl(x) printf("%lldn",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define STOP system("pause")
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }
template <class T>void tomin(T&a,T b){ a=min(a,b); }
ll sadd(ll a,ll b,ll c){
ll sum = 0;
while(b){
if(b&1) sum = (sum+a)%c;
a = (a+a)%c;
b>>=1;
}
return sum;
}
int main(){
ll a,b,c;
Scl3(a,b,c);
Prl(sadd(a,b,c));
}

最后

以上就是可靠手套为你收集整理的题解 | 《算法竞赛进阶指南》64位整数乘法的全部内容，希望文章能够帮你解决题解 | 《算法竞赛进阶指南》64位整数乘法所遇到的程序开发问题。

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