Day01 1.14 博客

T1. #Z2302 -- 64位整数乘法

题意简述

给定 $a,b,p$，求 $a \times b \bmod p$，其中 $1 \le a,b,p \le 10^{18}$。

解题思路

一眼高精度啊（但是老师不让用

考虑使用快速幂思想：

快速幂思想：$a^b=(a^2)^{\frac{b}{2}}$（$b$ 为偶数）

以此类推本题可以变为：$a \times b=(a \times 2)\times\frac{b}{2}$（$b$ 为偶数）

$b$ 为奇数时情况也类似，具体见代码。

正解代码

#include <bits/stdc++.h>
//push_back
#define int long long
using namespace std;
int a, b, p;

int qmul (int a, int b, int p)
{
	int res = 0;
	while (b)
	{
		if (b & 1) res = (res + a) % p; //和快速幂情况类似
		a = (a + a) % p;
		b >>= 1;
	}
	return res;
}

signed main ()
{
    cin >> a >> b >> p;
	cout << qmul (a, b, p);
	return 0;
}

注意：灵活运用各种学过的算法的 思！想！