欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 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;
} 

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