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 \\ \end{bmatrix}$ 就可以了

然后由出现了一个问题
我们需要取膜（雾）
要知道 $a^b$ 所以我们需要欧拉定理
$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));
    }
}