关于快速幂取余运算问题

p次方求和

描述

一个很简单的问题，求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

# include <stdio.h>

int pow(int x, int y, int z);

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, p, i;
        int sum = 0;
        scanf("%d %d", &n, &p);

        for (i=1; i<=n; i++)
          sum += pow(i, p, 10003);

        printf("%dn", sum%10003);
    }

    return 0;
}

int pow(int x, int y, int z)  //x底数  y指数  z取余的数
{
	int ans = 1;
	x = x % z;        //之前一定要对x取余，因为这样不会影响结果，而且减小运算量
	while (y > 0)
	{
	    if (y % 2 == 1)             //如果要是奇数次方的话，先让ans乘上一个x
                  ans = ( ans * x ) % z;    

           x = (x * x) % z;           //让x自乘，y减半  然后迭代
	    y /= 2;

	}

	return ans;              //可能你会有疑问，为什么返回的是ans  这是因为无论次幂是奇数还是偶数
                                 //对它一直除以2的话，最后一定是一个1，然后就会乘到ans上边
}

最后

以上就是自信玉米为你收集整理的关于快速幂取余运算问题的全部内容，希望文章能够帮你解决关于快速幂取余运算问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。