题目描述
求 a 乘 b 对 p 取模的值。1≤a,b,p≤1e18
输入:
第一行输入整数a,第二行输入整数b,第三行输入整数p。
输出:
输出一个整数,表示a*b mod p的值。
样例
输入:
3
4
5
输出:
2
算法1
(暴力枚举) $O(1)$
思路:直接相乘。1≤a,b,p≤1e18,即使用unsigned long long也肯定会爆
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p;
int main(){
cin>>a>>b>>p;
cout<<a*b%p;
return 0;
}
算法2
(暴力枚举) $O(log b)$
思路:在上一题中我们用了二进制拆分。
用类似的方法,只需要把平方改成乘2就好了
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull a,b,p,ans;
int main(){
cin>>a>>b>>p;
for(;b;b>>=1){
if(b&1)ans=(ans+a)%p;
a=a*2%p;
}
cout<<ans;
return 0;
}