AcWing 90. 64位整数乘法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 90. 64位整数乘法原题链接简单

作者：

洛希krist , 2019-01-23 11:41:20 , 所有人可见 , 阅读 14491

78

22

题目描述

求 a 乘 b 对 p 取模的值。
数据范围
1≤a,b,p≤10^18

样例

输入样例：
3
4
5
输出样例：
2

算法1

(二进制思想) $O(logn)$

如果直接计算a乘b这会超过 long long 的最大范围，所以采用类似于快速幂的思想
把 b写成二进制形式，然后如果某位上为1就加上它a*（2^n）次方（n与这位的位置有关）
并且每次计算后取模就可以了

例：计算 3*7

7的二进制 111
3*(2^0)=3
3*(2^1)=6
3*(2^2)=12

观察可发现每次的可由前一次*2推出(记得取模)

时间复杂度分析：logn

C++ 代码

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
int main()
{
    ll a,b,p,res;
    cin>>a>>b>>p;
    res=0;
    while(b)
    {
        if(b&1)
            res=(res+a)%p;
        b>>=1;
        a=2*a%p;
    }
    cout<<res<<endl;
    return 0;
}

33 评论

辣鸡号航母 2022-07-26 22:50

就没人写高精度吗

歪歪歪 6个月前

我写了，不会取余，能看看大佬的代码吗

辣鸡号航母 6个月前回复了歪歪歪的评论

https://www.acwing.com/activity/content/code/content/3921964/

歪歪歪 6个月前回复了辣鸡号航母的评论

懂了，谢谢大佬

Liyunze123 1个月前

## 算法2
做乘法时转换为__int128，取模后转回 long long
代码：

#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
int main(){
    cin>>a>>b>>p;
    long long ans=(__int128)a*b%p;
    printf("%lld\n",ans);
    return 0;
}

frt 5个月前

1.高精度
2.128int
3.二进制思想

317 2022-03-28 11:38

请问这个慢速乘，是专门用来解决爆long long的吗？有其他的应用吗？

Kunikun 2019-07-22 17:25

很棒！

秦淮岸灯火阑珊 2019-01-23 19:59

赞一下

洛希krist 2019-04-09 11:30

谢谢啦，看了你的很多题解👍

duanyq 2023-09-24 22:24

Soel 2023-07-31 07:23

留下一个思维深度极高的版本

template <class T>
T mul(T a, T b, auto mod) {
    if (b == 0) return 0;
    T kt = mul(a, b >> 1, mod);
    kt = (kt + kt) % mod;
    if (b & 1) kt = (kt + a) % mod;
    return kt;
}