AcWing 90. 64位整数乘法（位运算）

电玩女神 2022-11-12 10:53 136阅读 0赞

**上一篇博客：[AcWing 89. a^b（快速幂）][AcWing 89. a_b]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 90. 64位整数乘法][AcWing 90. 64]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  解题思路
     *  解题代码

# 题目信息 #

## 题目描述 ##

求 **a** 乘 **b** 对 **p** 取模的值。

## 输入格式 ##

第一行输入整数 **a**，第二行输入整数 **b**，第三行输入整数 **p**。

## 输出格式 ##

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

## 数据范围 ##

**1 ≤ a, b ,p ≤ 1018**

## 输入样例 ##

> **3  
> 4  
> 5**

## 输出样例 ##

> 2

# 题解 #

## 解题思路 ##

本题类似于 `快速幂` 的思想，如果直接将两个数相乘的话，那么两个数最大的乘积为 **1036**，会爆 `long long`。但是用位运算则不会。主要的思路为将相乘改变为相加。比如要计算 **13 \* 8**，将 **8** 转换为二进制为：**1000**，可以表示为： 0 ∗ 2 0 + 0 ∗ 2 1 + 0 ∗ 2 2 + 0 ∗ 2 3 0 \* 2^0 + 0 \* 2^1 + 0 \* 2^2 + 0 \* 2^3 0∗20\+0∗21\+0∗22\+0∗23。那么 **13 \* 8** 可以表示为：**13 \* ( 0 ∗ 2 0 + 0 ∗ 2 1 + 0 ∗ 2 2 + 1 ∗ 2 3 0 \* 2^0 + 0 \* 2^1 + 0 \* 2^2 + 1 \* 2^3 0∗20\+0∗21\+0∗22\+1∗23)**。

所以可以通过递推求出每个乘积项，然后将结果累加起来即可。每次递推都判断 **b** 的最后一位是否是 **1**，如果是 **1** 说明当前的乘积项需要加上，否则说明不需要加。继续计算下一个乘积项，每次都使 **a = a \* 2 % p** 即可，这样就可以得出每一个乘积项。判断完成后将 **b** 右移一位，继续进行下一次运算。

因为每次都会对结果取模，所以不会出现数据溢出的情况。该算法的时间复杂度为：**O(log2N)**。

## 解题代码 ##

#include<iostream>
    using namespace std;
    
    typedef unsigned long long ULL;
    
    int main() { 
        ULL a, b, p;
        cin >> a >> b >> p;
        ULL ans = 0;
        while (b) { 
            if (b & 1) ans = (ans + a) % p;
            b >>= 1;
            a = a * 2 % p;
        }
        cout << ans;
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70][]

[AcWing 89. a_b]: https://ac-fun.blog.csdn.net/article/details/115122613
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 90. 64]: https://www.acwing.com/problem/content/92/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221022/4b640466bac7423e83b57c55ee0a7de3.png