牛客網 64位元整數乘法

題目描述

求 a 乘 b 對 p 取模的值，其中 1≤a,b,p≤10¹⁸。
輸入描述:
第一行a，第二行b，第三行p。
輸出描述:
一個整數，表示a×b mod p的值。
範例1
輸入
2
3
9
輸出
6
題目鏈接：https://ac.nowcoder.com/acm/contest/996/C
來源：牛客網

解析

很顯然，直接返回a*b%p勢必會出現乘法溢位的情況！借鑑快速冪的思想，可以得到如下解決方案：
1.將a*b改爲b個a相加，不斷對a做"a=a+a"的迭代，可依據b選擇對應的迭代值a加入到累加值res中，使得res恰好爲初始a值的b倍。
2.由於模運算存在這樣一個性質：(a+b)%p=(a%p+b%p)%p。同樣可以推廣到（a+b+c+…)%p=(a%p+b%p+c%p+…)%p。用文字表述就是任意多個加數相加後再取模等於各加數取模後相加再取模。故只需要每一步都對加數（a+a）取模，每一步都對「各加數取模後相加」得到的（res+a）取模。如此就防止了乘法的溢位，同時快速冪的思想也保證了較低的時間複雜度。
附上之前寫的快速冪詳解！(通俗易懂)，以做對比學習。

AC程式碼

#include<iostream>
using namespace std;
typedef long long LL;
 LL multi(LL a,LL b,LL p){    
 LL res=0;
 while(b>0){
 if(b&1) res=(res+a)%p;  / /對「各加數取模後相加」得到的（res+a）取模
 a=(a+a)%p;             / /對加數（a+a）取模
 b=b>>1;
 }    
 return res;    
 }
int main(){     
LL a,b,p; 
cin>>a>>b>>p;   
cout<<multi(a,b,p);    
  return 0;  
}