p次方求和

時間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述

一個很簡單的問題，求1^p+2^p+3^p+……+n^p的和。 輸入

第一行單獨一個數(shù)字t表示測試數(shù)據(jù)組數(shù)。接下來會有t行數(shù)字，每行包括兩個數(shù)字n,p，
輸入保證0<n<=1000,0<=p<=1000。

輸出

輸出1^p+2^p+3^p+……+n^p對10003取余的結(jié)果，每個結(jié)果單獨占一行。

樣例輸入

2 10 1 10 2

樣例輸出

55 385 這個題求n的p次方是個難點，因為p會取到1000，平常求冪次方的求法肯定是不行的，所以就要優(yōu)化。最簡單的優(yōu)化方法就是用二進制優(yōu)化，具體怎樣不在詳細說明，百度一下，你就知道。 #include<stdio.h> #include<math.h> long long fun(int a, int b) //求a的b次方 {long long s=1;while(b!=0){if(b&1) //b%2==1s=s*a%10003;a=a*a%10003;b>>=1;}return s; } int main() {int t,n,p,i;scanf("%d",&t);while(t--){scanf("%d%d",&n,&p);if(n==1){printf("1\n");continue;}else if(n==0){printf("0\n");continue;}else if(p==0){printf("%d\n",n);continue;}else{long long sum=1; //因為1的任何次冪都是1，所以直接令sum=1，節(jié)省時間for(i=2;i<=n;i++)sum+=fun(i,p);printf("%lld\n",sum%10003);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 420 p次方求和 大数的幂的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。