跟着姚桑学算法-64位整数乘法

基本算法题. 64位整数乘法

求 a 乘 b 对 p 取模的值。

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

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

数据范围
1≤a,b,p≤1018

输入样例：

3
4
5

输出样例：

2

:four_leaf_clover:题解 --- 二进制思想

如果直接计算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推出

:memo:代码展示

#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;
}

【知识点：二进制思想】

二进制只有0和1两个数字，基数为2，在加减法运算中，逢二进一，借一当二。

• 表示数值：0、1、10、111、100、1000001
• 加法：1+0=1、1+1=10、10+110=1000、111+111=1110
• 减法：1-0=1、10-1=1、100-11=1、1010-101=101

这里补充回顾一下我们日常使用的十进制与二进制之间的转换：

• 十进制 4321 = 4×103 + 3×102 + 2×101 + 1×100
• 二进制 1101 = 1×23 + 1×22 + 0×21 + 1×20 = 8 + 4 + 0 + 1 = 13
• 二进制 110.11 = 1×22 + 1×21 + 0×20 + 1×2-1 + 1×2-2 = 4 + 2 + 0 + 0.5 + 0.25 = 6.75

我们要记住，任何信息在计算机中都是采用二进制表示的，数据在计算机中是以补码形式存储的，位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在竞赛中往往可以优化理论时间复杂度的系数。同时，一个整数的各个二进制位互不影响，利用位运算的一些技巧可以帮助我们简化程序代码。