poj 1995 Raising Modulo Numbers 快速幂

缘起

日常浪费生命 poj 1995 Raising Modulo Numbers

分析

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
求(A1^B1 + A2^B2 + ... +Ah^Bh)%M

【输入】
多样例. 第一行是样例数. 每个样例的第一个正整数是M（1 <= M <= 45000）,H(1 <= H <= 45000).
然后是H行，每行两个数字A和B（不全为零）

【输出】
对于每个样例，输出结果

【样例输入】
3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

【样例输出】
2
13195
13

【限制】
1s

裸题快速幂，没什么好说的

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
42
43
44
45
46
47
48
49
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
typedef long long LL;

LL m,h,a,b;

LL q(LL a, LL b, LL mod) // 计算 a^b 模掉mod的余数
{
	LL ans = 1;
	a%=mod;
	while(b)
	{
		if (b&1)
		{
			ans = ans*a%mod;
		}
		if (b>1)
		{
			a = a*a%mod;
		}
		b>>=1;
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		LL ans = 0;
		scanf("%lld%lld", &m, &h);
		while(h--)
		{
			scanf("%lld%lld",&a, &b);
			ans+=q(a,b,m);
			ans%=m;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 125ms
Memory 96kB
Length 590
Lang C++
Submitted 2019-09-01 14:10:48
Shared
RemoteRunId 20823274