64位整数乘法 题解

题意分析

给你两个整数a,b，都在级别，要求你计算的值。p也是级别的。

解题思路

这题如果用普通的乘法，要么就只能用__int128，这个是不被允许的。

• 接下来我们可以对乘数中的其中一个进行二进制拆分，例子如下：
  1. 
  2. 
• 在计算机中，二进制能够表示所有的整数。大家都知道，我在这里把这个49表示为。这就是这个程序的实现过程所在了，进一步化简：
  • 。
  • 这个时候可以再演示一次“”，
  • ，可化为。
• 现在思路是不是很明显了？
  • 无非就是先把乘数中间的一个进行二进制拆分，然后做“加法”来实现乘法。
  • 其中一个乘数不断取余数，如果当前余数是1代表该乘数当前二进制位上有“1”，进行“加法”累加进总答案。

参考程序

#include<bits/stdc++.h>
using namespace std;
long long n,answ,b,MOD;
int main()
{
    cin>>n>>b>>MOD;
    long long answ=0;
    while(b)
        {
            if(b%2==1)
                answ=(answ+n)%MOD;
                //“二进制位”上如果是1，则+“基数”。
            n=(n*2)%MOD;
            //“基数”不断加倍，想想一开始是2，然后是4，然后是8，……
            b/=2;
            //对其中一个乘数不断÷2
        }
    cout<<answ;
    return 0;
}