关于快速幂取余运算问题

81 阅读 0 评论 54 点赞

我是靠谱客的博主自信玉米，这篇文章主要介绍关于快速幂取余运算问题，现在分享给大家，希望可以做个参考。

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取余的结果，每个结果单独占一行。

样例输入

复制代码

1
2

复制代码

1
10 1

复制代码

1
10 2

样例输出

复制代码

1
55

复制代码

1
385

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 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上边
}