基础算法题——学长的白日梦(快速幂、快速逐步求积)
程序员文章站
2022-06-08 12:10:05
...
学长的白日梦
题目简单明了,只要将计算出 xi 即可。
两个卡点:
①、快速幂
②、快速逐步求积
由于这道题 mod = 999999997 。mod * mod > 10^19,不能直接用快速幂解决,中间求积会爆。于是我卡在逐步求余上动弹不得,唉~
看了题解后发现在快速幂中高效地实现逐步求积即可解决问题,代码思想与快速幂异曲同工。就很妙,很舒服。
//快速逐步求积
long long quick_mul(long long a, long long b){
ll ans = 0;
while(b){
if(b%2) ans = (ans+a)%mod;
a = (a+a)%mod;
b >>= 1;
}
return ans;
}
//快速幂
long long quick(ll base, ll power){
ll ans = 1;
while(power){
if(power%2) ans = quick_mul(ans, base);
base = quick_mul(base, base);
power >>= 1;
}
return ans;
}
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 9999999967;
ll dp[15][10010];
ll quick_mul(ll a, ll b){
ll ans=0;
while(b){
if(b%2) ans = (ans+a)%mod;
a = (a+a)%mod;
b>>=1;
}
return ans;
}
ll quick(ll base, ll power){
ll ans = 1;
while(power){
if(power&1)
ans = quick_mul(base, ans)%mod;
base = quick_mul(base, base)%mod;
power >>= 1;
}
return ans;
}
int main(){
int t;
cin>>t;
while(t--){
ll x, i, ans=1;
cin>>x>>i;
cout<<quick(x, i)<<endl;
}
return 0;
}
回顾学习一年前开始算法到现在,我发现我在途中丢了那份热情、单纯,没能享受算法带来的乐趣。
算法应该是有趣的,富有活力的,我不应当丢失,回归初心,方得始终。
上一篇: 理解Angular中的数据绑定
下一篇: Angular的表达式