【問題描述】
題目很簡單：請你計算(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)新聞熱點
疑難解答
圖片精選
