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

怼烎@ 2022-11-21 01:22 131阅读 0赞

#### [学长的白日梦][Link 1] ####

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

--------------------

题目简单明了，只要将计算出 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;
    }

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

[Link 1]: https://ac.nowcoder.com/acm/contest/7872/F
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/aa29a22781c44437b87e1b3dd19baaf1.png