I-迷途的怪物

NC200312. I-迷途的怪物

描述

圣杯能召唤过去，现在甚至未来的各种英灵。想必也有不同世界的英灵会被召唤，所以才会有对圣杯的不断响应吧。为了修复过去的错误。为了重新选择。
「吾名奥德修斯，为七骑之中的狂战士(berserker)」面前的怪物开口了，虽然具有人形，但却没有一点人的感觉。更像是失控的野兽。
「还保有理智吗」
「是的」怪物没有过多的行动「开门见山吧，吾辈是没有战胜魔女喀耳刻的奥德修斯。我不曾再见过我的妻儿，被魔女任意改造成可怕的怪物。因为同为奥德修斯而被记录在英灵座上的怪物罢了。我不打算和你们动手，但你们必须回答我的问题，才能离开。无法得到答案，连我也无法离开这个迷宫」
「请说」
「迷宫的一个岔口对应一个谜题，而这些谜题的答案都是由一个公式计算得到的，这个公式就是(p-1)ⁿ % p。每个岔口都有对应的p和n，而且p必定为一个素数。带着我，只要你计算出正确答案，我就能告诉你正确的前进方向」它起身了
「我明白了」虽然它给我感觉是失控的野兽，但却毫无危险的感觉

输入描述

第一行输入一个整数T (1<=T<=5)，代表有T个样例，
对于每组样例，输入一行，每行输入一个质数p (2<=p<=10⁹)和一个整数n (0<=n<10^1000001 )。

输出描述

对于每一组样例，输出(p-1)ⁿ % p
（注：'%'是取模运算符，也叫取余运算符，比如：8 % 3 = 2，因为8除于3的余数是2。更详细的说：因为8 = 2*3 + 2，前一部分 "2*3" 是3的倍数，后一部分 "2" 是小于3的数，后一部分就是8 % 3的结果）

示例1

输入:

2
2 1
2 2

输出:

1
1

说明:

提示：n会很大，请不要试图使用int和long long存，要用char数组存。另外，请不要执行1e7次及以上的取模运算，否则超时。

输入输出代码(参考)：

#include <stdio.h>

char n[1000005];

int main()
{
int T;
scanf("%d", &T);
for(int t = 1; t <= T; t++)
{
int p;
scanf("%d %s", &p, n);

//...;

//printf...;

}

return 0;
}

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 244ms, 内存消耗: 6232K, 提交时间: 2019-12-09 21:05:28

#include <bits/stdc++.h>
using namespace std;
char n[1000005];
int main()
{
int T;
cin>>T;
for(int t = 1; t <= T; t++)
{
int p;
cin>>p;
cin>>n;
if((n[strlen(n)-1]-'0')%2==0)
cout<<1<<endl;
else
cout<<p-1<<endl;
}
return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 166ms, 内存消耗: 2440K, 提交时间: 2019-12-07 21:46:30

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T,m,p;
	string n;
	cin>>T;
	while(T--){
		cin>>p>>n;
		m=(n[n.length()-1]-'0')&1;
		cout<<(m?p-1:1)<<endl;
	}
	return 0;
}

Ruby(2.4.2) 解法, 执行用时: 63ms, 内存消耗: 14600K, 提交时间: 2019-12-07 22:41:58

T = gets.to_i
T.times do
	p, n = gets.split
	if n[-1].to_i & 1 == 1
		puts p.to_i - 1
	else
		puts 1
	end
end

Python3(3.5.2) 解法, 执行用时: 50ms, 内存消耗: 11156K, 提交时间: 2019-12-11 00:58:18

for i in range(int(input())):
	c = input().split()
	print(1 if(int(c[1][-1])%2==0) else int(c[0])-1)