题解 | #Look Up#

64位整数乘法

https://ac.nowcoder.com/acm/problem/50908

思路:
数据范围为1—1e18.直接取模相乘肯定会爆。这里我们考虑一个性质:a*2*b/2=a*b;
我们知道a*2<1e20.所以我们可以对a倍增,b倍减。
话不多说,上算法:
ll ans=0;    
    while(b)
    {
        if(b&1){ans=(ans+a)%p;}    
        a=(a*2)%p;
        b>>=1;
    }
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll a,b,p;
int main(void)
{
    ll ans=0;
    cin>>a>>b>>p;
    
    while(b)
    {
        if(b&1){ans=(ans+a)%p;}    
        a=(a*2)%p;
        b>>=1;
    }
    cout<<ans;
}




全部评论

相关推荐

offer多多的六边形战士很无语:看了你的博客,感觉挺不错的,可以把你的访问量和粉丝数在简历里提一下,闪光点(仅个人意见)
点赞 评论 收藏
分享
10-15 09:13
已编辑
天津大学 soc前端设计
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务