题目描述

求 a 乘 b 对 p 取模的值。

数据范围: 1≤a,b,p≤10^18

难度： 简单

样例

sample input: 3 4 5

sample output: 2

算法1

(快速幂思想) $O(log2 b)$

举样例的例子吧！

设a=3,b=4,c=5,ans为最后的结果;
b可以跟快速幂一样，表示为二进制，b=4=(100)2;
34可以看作是:
(3*2*2+0*2+0*1)=12
所以如果当前b&1==1,ans=(ans+a)%p,并a=2a%p,
否则a=2*a%p.
每操作完一步,都要将b右移一位(b>>=1),
直到b=0.

----> 特别坑的一个地方:要开long long!!! <----

C++ 代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int mulitply(int a,int b,int p)
{
    int ans=0;
    while(b)
    {
        if(b&1)ans=(ans+a)%p;
        b>>=1;
        a=2*a%p; 
    }
    return ans;
}
int main()
{
  LL a,b,p;
  cin>>a>>b>>p;
  cout<<mulitply(a,b,p)<<endl;
}

题目链接🔗