题解 | #64位整数乘法#

题目分析

题面比较简单，求 $a\times b \mod p$ 的值。但是问题在于数值较大，是 $10^{18}$ 的数量级，我们当前的 int 和 long long是存不下 $a\times b$ 的。

方法1

既然整数类型 int 与 long long 存储不下的话，是否存在更大的整数类型可以存下 $a\times b$ 呢？此时我们引入数据类型 __int128 该类型有 $128$ Byte，完全放得下 $a\times b$ 的值。需要注意的是，__int128 仅 GCC4.6 以上 64位版本知识，且不在 C++ 标准中，只能进行四则运算无法使用cin、cout进行输入输出。

在本题中我们可以先用 long long 类型变量存储 $a,b,p$ 再复制到 __int128 中进行计算，由于最后是 %p所以可以把结果存储到long long类型数据中进行输出。

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
const int N = 1e5 + 5;
int main() {
  i64 a, b, p;
  cin >> a >> b >> p;//先用long long类型输入、存储a,b,p
  i128 A = a, B = b;//复制a,b到A,B中
  i64 ans = A * B % p;//将算出的结果保存在long long中
  cout << ans;
  return 0;
}

方法2

__int128 使用具有一定的局限性，是否存在其他的方式进行处理呢？我们可以从二进制的角度进行观察。

设 $b$ 的 $m$ 位二进制表达为 $x_{m-1}x_{m-2}\cdots x_2x_1x_0$ 。那么根据进制转换的处理， $b=x_02^0 x_12^1 x_22^2 \cdots x_{m-1}2^{m-1}$ 。那么

alt

可发现对于 $b$ 将它拆分成了有限的几个部分，并结合乘法、加法的结合律将两个大数的乘法转换成了有限的几个乘积的和，并配合同余的性质从而避免了溢出。

过程中对于 $2^m$ 的计算，可以利用递推的方式进行求解。 $2^m=2^{m-1}\times 2$ 。

此时，我们只需要对 $b$ 的二进制进行遍历，看对应二进制位上是否是 $1$ ，如果为 $1$ 则累加对应的 $2$ 的次幂。

配合位运算操作，可以实现对二进制的遍历。 x & 1 可以判断当前 $x$ 的最低位是否为 $1$

//遍历 x 的二进制位
while(x){
    if(x&1){
        //判断 x 当前的最低位是否为1
    }
    x>>=1;//将x的二进制右移一位
}
/*
x=(10110)2
x>>=1

x=(01011)2
x>>=1

x=(00101)2
x>>=1

x=(00010)2
x>>=1

x=(00001)2
x>>=1

x=(00000)2
*/

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 5;
i64 lowbit(i64 x) { return x & -x; }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  i64 a, b, p, ans = 0;
  cin >> a >> b >> p;
  a %= p;
  b %= p;
  while (b) {
    if (b & 1) {//判断当前b的二进制最低位是否为1
      ans = (ans + a) % p;//为1则累加 a* 2的次幂
    }
    a = a * 2 % p;//更新对应位置的项数，a*2^m = a*2^{m-1}*2
    b >>= 1;//将b的二进制右移一位
  }
  cout << ans;
  return 0;
}