AcWing 90. 快速幂思维,__int128运用
原题链接
简单
作者:
梦念小袁
,
2023-10-08 21:53:20
,
所有人可见
,
阅读 53
方法一:使用快速幂类似的思维
// 解题思路直接乘法会导爆LL 所以我们使用同快速幂的方式来把乘法变为加法即可
LL quick_add(LL a,LL b,LL p){
LL res=0;
while(b){
if(b&1) res=(res+a)%p;
b>>=1;
a=(a+a)%p;
}
return res;
}
void solve(){
LL a,b,p;
cin>>a>>b>>p;
cout<<quick_add(a,b,p)<<endl;
return ;
}
int main(){
int _; _=1;
while(_--) solve();
return 0;
}
方法二:使用__int128来处理不会太大的数
// 考虑到实际上成绩不会爆__int128我们可以直接使用__int128作为过度加上强制转化即可
void print(__int128 x){
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+'0');
}
void solve(){
LL a,b,p;
cin>>a>>b>>p;
__int128 res=(__int128)a*b%p;
print(res);
return ;
}
int main(){
int _; _=1;
while(_--) solve();
return 0;
}