暑假在看c++面经时,看到了腾讯的一道面试题。
题目大意是:求(2^1e10)%10000的值,限制了时间复杂度。
在C++中没有Java和Python中的大数,不知道读者朋友们可否AC此题。
这道题可以用快速幂来AC。
请听我详细道来。
在学习了二进制相关知识后,我们知道任何一个数都可以用唯一的二进制表示,也就是说每一个数可以唯一表示为若干指数不重复的2的次幂的和。
举个例子:假设b在二进制表示下有k位。则b可以表示为:
b=ck-12k-1+ck-22k-2+ck-32k-3+......+c121+c020
给定a,b,p的值,求(a^b)%p的值。a,b,p都是大数,1<= a ,b ,p<=1e10.
给定a,b,p的值,求(a*b)%p的值。a,b,p都是大数,1<= a ,b ,p<=1e10.
有上面的例子可知:
b=ck-12k-1+ck-22k-2+ck-32k-3+......+c121+c020
则 a^b= ac~k-1~2k-1+ac~k-2~2k-2+ac~k-3~2k-3+......+ac~1~21+ac~0~20
由于数学格式支持的不是很好,贴一个图说明一下。
根据上式我们发现,原问题被我们转化成了形式相同的子问题的乘积,并且我们可以在常数时间内从2k-1项推出 2k项。
这个算法的复杂度是O(logN) 的,我们计算了logN个 2K次幂的数,然后花费 logN 的时间选择二进制为 1 对应的幂来相乘。
#includeusing namespace std; typedef long long LL; LL a,b,p; int main() { scanf("%lld%lld%lld",&a,&b,&p); LL ans=1%p; // 初始ans while(b) { if(b&1) ans=ans*a%p; a=a*a%p; //反复平方 b>>=1; } printf("%lld\n",ans); return 0; }
同第一张模板类似,同理:
#includeusing namespace std; typedef long long LL; LL a,b,p; LL ans; int main() { scanf("%lld%lld%lld",&a,&b,&p); while(b) { if(b&1) ans=(ans+a)%p; // 累加每个2^k a=a*2%p; b>>=1; } printf("%lld\n",ans); return 0; }
由于快速幂的数据很大,在使用c++做题时,用单纯的cin来输入测试用例很慢,会导致超时。
在这里给两个小建议:
cin前面加上这条取消同步的语句
cin.tie(nullptr)->sync_with_stdio(false);
用scanf()来读取。
关于快速幂的题型还有很多,比如快速幂矩阵,计算斐波那契数等。
这篇文章所讲的只是快速幂的初阶内容,我在后面会为大家分享更高阶的快速幂知识。
联系客服