POJ 1995 Raising Modulo Numbers

题目传送门:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1995

以下是AC代码:

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
// Author: Tanky woo
// POJ 1995
// www.wutianqi.com
#include <iostream>
using namespace std;
 
int nCases;
__int64 nNum, M, H, a, b;
 
__int64 exp_mod(__int64 a, __int64 n, __int64 b)
{
    __int64 t;
    if(n==0) return 1%b;
    if(n==1) return a%b;
    t=exp_mod(a,n/2,b);
    t=t*t%b;
    if((n&1)==1) t=t*a%b;
    return t;
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d", &nCases);
	while(nCases--)
	{
		__int64 ans = 0;
		scanf("%I64d %I64d", &M, &H);
		while(H--)
		{
			scanf("%I64d %I64d", &a, &b);
			ans += exp_mod(a, b, M);
			ans %= M;
		}
		printf("%I64d\n", ans);
	}
	return 0;
}

具体分析见:
快速幂取模

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《POJ 1995 Raising Modulo Numbers》有5个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注