题解 | #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;
}
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;
}
投递地平线等公司10个岗位 >
