【C++心路历程23】求幂的和分治算法

2019-11-10 18:09:34

字体：大中小

来源：转载

供稿：网友

【问题描述】

　　题目很简单：请你计算(a^1+a^2+…+a^n) mod 1234567 的结果，其中（0 < a,n < 2^31 ）。

【输入格式】

第一行T，表示数据组数，接下来的T行，每行包含a和n，表示一组数据。

【输出格式】

对于每组数据，输出对应的答案。

【输入样例】

5 1 7 3 10 5 8 9 20 17 100

【输出样例】

7 88572 488280 696766 550479

【数据范围】

0< T <=1000 【分析】首先不难想到直接用二分快速幂求解，算出每个幂的值后相加。时间复杂度分析：O（T*log2（n！））在本题n < 2^31，T <=1000不能通过全部数据。其次能想到等比数列运用公式直接求解，但本题数据规模较大，且运用除法不能取模，所以得想想其他的方法— — 由a^1+a^2+…+a^n，如果将这个式子二分，得到（a^1+a^2+…+a^（n/2））*（1+a^（n/2））；则本题就迎刃而解了，运用分治不断递归求解即可。参考：

#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>using namespace std;int T,mo=1234567;long long qkpow(int a,int p){ if(p==0) return 1; long long t=qkpow(a,p/2); if(p%2==1) return t*t%mo*a%mo; else return t*t%mo;}long long solve(int a,int n){ int m=n/2; if(n==1) return a%mo; long long ans=solve(a,n/2)*(qkpow(a,n/2)+1)%mo; //递归计算（a^1+a^2+…+a^（n/2））*（1+a^（n/2）） if(n%2==1) ans=(ans+qkpow(a,n))%mo; return ans; }int main(){// freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { int a,n; scanf("%d%d",&a,&n); if(a==1) PRintf("%d/n",n); else { long long ans=solve(a,n); cout<<ans<<endl; } } return 0;}

上一篇：c++==与c关键字的对比(2)

下一篇：C++命名空间