题目描述 求 a 乘 b 对 p 取模的值。 数据范围 1≤a,b,p≤10^18
样例 输入样例： 3 4 5 输出样例： 2 算法1 (二进制思想)
如果直接计算a乘b这会超过 long long 的最大范围，所以采用类似于快速幂的思想 把 b写成二进制形式，然后如果某位上为1就加上它a*（2^n）次方（n与这位的位置有关） 并且每次计算后取模就可以了
例：计算 3*7
7的二进制 111 3*(2^0)=3 3*(2^1)=6 3*(2^2)=12
观察可发现每次的可由前一次*2推出(记得取模)
时间复杂度分析：logn
代码语言：javascript复制#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
int main()
{
ll a,b,p,res;
cin>>a>>b>>p;
res=0;
while(b)
{
if(b&1)
res=(res a)%p;
b>>=1;
a=2*a%p;
}
cout<<res<<endl;
return 0;
}
