首页 > 代码库 > NYOJ 420 p次方求和 （快速幂+同余定理）
NYOJ 420 p次方求和 （快速幂+同余定理）
题目描述：
http://acm.nyist.net/JudgeOnline/problem.php?pid=420
- 一个很简单的问题，求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取余的结果，每个结果单独占一行。
- 样例输入
210 110 2- 样例输出
55385
题目分析：
快速幂+同余定理的问题，虽然已经写了好多次的快速幂但是还是没有记住，每次都是看模板，这次一定记住它。
AC代码：
/**
*快速幂取摸+同余
*/
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
int mod(int a,int b,int n){
int t = 1;
if (b == 0)
return 1;
if (b == 1)
return a%n;
t = mod(a, b>>1, n);
t = t*t % n;
if (b&1){//b是奇数
t = t*a % n;
}
return t;
}
int main()
{
int t;
cin>>t;
while(t--){
int p,n;
cin>>n>>p;
int res=0;
for(int i=1;i<=n;i++){
int t=mod(i,p,10003);
//cout<<t<<endl;
res=(res%10003+t%10003)%10003;
}
cout<<res<<endl;
}
return 0;
}
NYOJ 420 p次方求和 （快速幂+同余定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。