p次方求和

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描述

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

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

輸出

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

樣例輸入

2 10 1 10 2

樣例輸出

55

385

解題思路：快速冪水過

AC:

#include<iostream> #include<cstdio> #include<cmath> using namespace std;const int mod = 10003; int power(int n,int p) {int ans = 1;while(p){if(p & 1) ans = ans * n % mod;n = n * n % mod;p >>= 1;}return ans; } int main() { int t,n,p,ans;cin>>t;while(t--){cin>>n>>p;if(p == 0){printf("%d\n",n);continue;}ans = 0;for(int i = 1; i <= n; i++)ans = (ans + power(i,p)) % mod;cout<<ans<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 420（快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。