基础算法题——学长的白日梦（快速幂、快速逐步求积）

学长的白日梦

题目简单明了，只要将计算出 xⁱ 即可。

两个卡点：
①、快速幂
②、快速逐步求积

由于这道题 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;
} 

回顾学习一年前开始算法到现在，我发现我在途中丢了那份热情、单纯，没能享受算法带来的乐趣。
算法应该是有趣的，富有活力的，我不应当丢失，回归初心，方得始终。