題目
求 a a a 乘 b b b 對 p p p 取模的值。
輸入格式
第一行輸入整數(shù) a a a，第二行輸入整數(shù) b b b，第三行輸入整數(shù) p p p。
輸出格式
輸出一個整數(shù)，表示 a*b mod p 的值。
數(shù)據(jù)范圍
1 ≤ a , b , p ≤ 1 0 18 1≤a,b,p≤10^{18} 1≤a,b,p≤1018
輸入樣例
3
4
5
輸出樣例
2
思路
C++ 內(nèi)置的最高整數(shù)類型是 64 位，現(xiàn)在 a ? b a * b a?b mod p p p 中的三個變量 a , b , p a, b, p a,b,p 都在 1 0 18 10^{18} 1018 級別，則不存在一個可供強制轉(zhuǎn)換的 128 位整數(shù)類型，需要一些特殊的處理辦法。
類似快速冪的思想，把整數(shù) b b b 用二進制表示，即 b = c k ? 1 2 k ? 1 + c k ? 2 2 k ? 2 + . . . + c 0 2 0 b = c_{k-1}2^{k-1} + c_{k-2}2^{k-2} + ... + c_02^0 b=ck?1?2k?1+ck?2?2k?2+...+c0?20，則 a ? b = c k ? 1 ? a ? 2 k ? 1 + c k ? 2 ? a ? 2 k ? 2 + . . . + c 0 ? a ? 2 0 a * b = c_{k-1} * a * 2^{k-1} + c_{k-2} * a * 2^{k-2} + ... + c_{0} * a * 2^{0} a?b=ck?1??a?2k?1+ck?2??a?2k?2+...+c0??a?20。
因為 a ? 2 i = ( a ? 2 i ? 1 ) ? 2 a * 2^{i} = (a * 2 ^{i-1}) * 2 a?2i=(a?2i?1)?2，若已求出 a ? 2 i ? 1 a * 2^{i-1} a?2i?1 mod p p p，則計算 ( a ? 2 i ? 1 ) ? 2 (a * 2 ^{i-1}) *2 (a?2i?1)?2 mod p p p 時，運算過程中每一步的結(jié)果都不超過 2 ? 1 0 18 2 * 10^{18} 2?1018，仍然在 64 位整數(shù) long long 的表示范圍內(nèi)，所以很容易通過 k k k 次遞推求出每個乘積項。當 c i = 1 c_i = 1 ci?=1 時，把該乘積項累加到答案中即可。文章來源：http://www.zghlxwxcb.cn/news/detail-716423.html
時間復(fù)雜度為 O ( l o g 2 b ) O(log_2b) O(log2?b)。文章來源地址http://www.zghlxwxcb.cn/news/detail-716423.html
代碼
#include <cstdio>
using namespace std;
typedef long long ll;
ll mul(ll a, ll b, ll p) {
ll ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
b >>= 1;
a = a * 2 % p;
}
return ans;
}
int main() {
ll a, b, p;
scanf("%lld%ld%lld", &a, &b, &p);
printf("%lld\n", mul(a, b, p));
return 0;
}
到了這里，關(guān)于AcWing90. 64位整數(shù)乘法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
