Description
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想对一组数据进行加密，但他对程序设计不太感兴趣，请你帮助他设计一个数据加密程序。
Input
第一行读入m，p。其中m表示数据个数，p用来生成数列E。 以下有m行，每行有2个整数n，q。n为待加密数据，q为密钥。 数据范围: 0 < p n< 2^31 0 < q < p 0 < m <= 5000。
Output
将加密后的数据按顺序输出到文件 第i行输出第i个加密后的数据。
Sample Input
输入样例1
2 7
4 5
4 6
输入样例2
4 7
2 4
7 1
6 5
9 3
Sample Output
输出样例1
3
1
输出样例2
3
0
1
1
题解
设斐波那契数列的第i项为$F(i)$
斐波那契数列
可以发现$E[i]=p^F(i)$
所以我们的任务变为了求$F(i)$然后矩阵快速幂
$$
\begin{bmatrix}
1 & 1 \\
1 & 0 \\
\end{bmatrix}
$$
最后乘上$ \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} $ 就可以了
然后由出现了一个问题
我们需要取膜（雾）
要知道 $ a^b%p!=a^{b%p}%p $
所以我们需要欧拉定理
$$ a^{\phi{n}} \equiv 1 (mod n) $$
然后易得
$$ a^{b%\phi{p}} \equiv a^b (mod p) $$
使用条件是 a与p 互质
然后就可以了筛出素数
$ \sqrt{n} $求$\phi{n}$就行了
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
bool isnprime[1000005];
int prime[200005], Idx;
void Get_Prime()
{
isnprime[1] = 1;
for (int i = 2; i <= 1000000; i++)
{
if (!isnprime[i])
{
prime[++Idx] = i;
}
for (int j = 1; j <= Idx; j++)
{
if (prime[j] * i > 1000000)
break;
isnprime[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
long long Get_Phi(long long x)
{
if (x == 1)
return 0;
int i = 1;
int Sq = sqrt(x);
long long ans = x;
while (x != 1)
{
if (prime[i] > Sq)
{
ans = ans - ans / x;
break;
}
if (x % prime[i] == 0)
{
ans = ans - ans / prime[i];
while (x % prime[i] == 0)
x /= prime[i];
}
++i;
}
return ans;
}
long long phi;
class Matrix
{
public:
int n, m;
long long a[3][3];
Matrix(int n1, int m1)
{
n = n1, m = m1;
memset(a, 0, sizeof(a));
}
Matrix operator*(const Matrix &A)
{
Matrix ans(n, A.m);
for (int i = 1; i <= n; i++)
for (int k = 1; k <= A.m; k++)
{
for (int j = 1; j <= m; j++)
ans.a[i][k] += a[i][j] * A.a[j][k];
if (ans.a[i][k] >= phi)
ans.a[i][k] = ans.a[i][k] % phi/* + phi*/;
}
return ans;
}
Matrix operator^(const long long &b)
{
long long k = b;
Matrix ans(n, m);
for (int i = 1; i <= n; i++)
{
ans.a[i][i] = 1;
}
Matrix A = *this;
while (k)
{
if (k & 1)
ans = ans * A;
k >>= 1;
A = A * A;
}
return ans;
}
};
long long pow_mod(long long a, long long b, long long mod)
{
long long ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
int main()
{
freopen("password.in", "r", stdin);
freopen("password.out", "w", stdout);
long long m, p;
Get_Prime();
Matrix O(2, 2);
O.a[1][1] = O.a[1][2] = O.a[2][1] = 1;
Matrix L(2, 1);
L.a[1][1] = 1;
scanf("%lld%lld", &m, &p);
while (m--)
{
long long n, q;
scanf("%lld%lld", &n, &q);
if (q == 1)
{
printf("0\n");
continue;
}
int t = p - q;
if (t == 1)
{
printf("1\n");
continue;
}
phi = Get_Phi(q);
printf("%lld\n", pow_mod(p, ((O ^ n) * L).a[2][1], q));
}
}