1348: Encrypt
内存限制:128 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:4
解决:0
题目描述
Rivest是密码学专家。近日他正在研究一种数列E={E[1],E[2],……,E[n]},且
E[1]=E[2]=p(p为一个质数),
E[i]=E[i-2]*E[i-1](若2 < i <= n)。
例如{2,2,4,8,32,256,8192,……}就是p=2的数列。在此基础上他又设计了一种加密算法,该算法可以通过一个密钥q (q < p)将一个正整数n加密成另外一个正整数d,计算公式为:d=E[n] mod q。
现在Rivest想对一组数据进行加密,但他对程序设计不太感兴趣,请你帮助他设计一个数据加密程序。
输入
第一行两个整数m,p。其中m表示数据个数,p用来生成数列E。
以下有m行,每行有2个整数n,q。n为待加密数据,q为密钥。
规模:0 < p,n < 2^31;0 < q < p;0 < m <=5000。
输出
将加密后的数据按顺序输出,
第i行输出第i个加密后的数据。
样例输入 复制
2 7
4 5
4 6
样例输出 复制
3
1
提示
case2
input:
4 7
2 4
7 1
6 5
9 3
output:
3
0
1
1