【問題描述】
題目很簡單：請你計(jì)算(a^1+a^2+…+a^n) mod 1234567 的結(jié)果，其中（0 < a,n < 2^31 ）。
【輸入格式】
第一行T，表示數(shù)據(jù)組數(shù)，接下來的T行，每行包含a和n，表示一組數(shù)據(jù)。
【輸出格式】
對于每組數(shù)據(jù)，輸出對應(yīng)的答案。
【輸入樣例】
5 1 7 3 10 5 8 9 20 17 100
【輸出樣例】
7 88572 488280 696766 550479
【數(shù)據(jù)范圍】
0< T <=1000 【分析】 首先不難想到直接用二分快速冪求解，算出每個(gè)冪的值后相加。 時(shí)間復(fù)雜度分析：O（T*log2（n！））在本題n < 2^31，T <=1000不能通過全部數(shù)據(jù)。 其次能想到等比數(shù)列運(yùn)用公式直接求解，但本題數(shù)據(jù)規(guī)模較大，且運(yùn)用除法不能取模，所以得想想其他的方法— — 由a^1+a^2+…+a^n，如果將這個(gè)式子二分，得到（a^1+a^2+…+a^（n/2））*（1+a^（n/2））；則本題就迎刃而解了，運(yùn)用分治不斷遞歸求解即可。 參考：
#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; //遞歸計(jì)算（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)新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
