64位整数乘法
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
求 a 乘 b 对 p 取模的值，其中 1≤a,b,p≤10181 \leq a,b,p \leq 10^{18}1≤a,b,p≤1018。
输入描述:
第一行a，第二行b，第三行p。
输出描述:
一个整数，表示a×b mod p值。
示例1
输入
复制2 3 9
2 3 9
输出
复制6
6
思路：
由于a,b,p都很大，a*b会直接爆掉，所以要优化
利用位运算，a*b=a*1+a*2+a*4+a*8+a*16+***
有1就加
代码：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll a,b,p;
int main(){
cin.tie(0);
cin>>a>>b>>p;
ll res=0;
ll s=1;
while(b){
if(b&1)res=(res+a)%p;
b>>=1;
a=a*2%p;
}
cout<<res;
}