[BZOJ 1409] Password - NekoMio's Blog

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}$ 就行了

1
#include <cstring>
2
#include <cstdio>
3
#include <cmath>
4
using namespace std;
5
bool isnprime[1000005];
6
int prime[200005], Idx;
7
void Get_Prime()
8
{
9
    isnprime[1] = 1;
10
    for (int i = 2; i <= 1000000; i++)
11
    {
12
        if (!isnprime[i])
13
        {
14
            prime[++Idx] = i;
15
        }
16
        for (int j = 1; j <= Idx; j++)
17
        {
18
            if (prime[j] * i > 1000000)
19
                break;
20
            isnprime[i * prime[j]] = 1;
21
            if (i % prime[j] == 0)
22
                break;
23
        }
24
    }
25
}
26
long long Get_Phi(long long x)
27
{
28
    if (x == 1)
29
        return 0;
30
    int i = 1;
31
    int Sq = sqrt(x);
32
    long long ans = x;
33
    while (x != 1)
34
    {
35
        if (prime[i] > Sq)
36
        {
37
            ans = ans - ans / x;
38
            break;
39
        }
40
        if (x % prime[i] == 0)
41
        {
42
            ans = ans - ans / prime[i];
43
            while (x % prime[i] == 0)
44
                x /= prime[i];
45
        }
46
        ++i;
47
    }
48
    return ans;
49
}
50
long long phi;
51
class Matrix
52
{
53
  public:
54
    int n, m;
55
    long long a[3][3];
56
    Matrix(int n1, int m1)
57
    {
58
        n = n1, m = m1;
59
        memset(a, 0, sizeof(a));
60
    }
61
    Matrix operator*(const Matrix &A)
62
    {
63
        Matrix ans(n, A.m);
64
        for (int i = 1; i <= n; i++)
65
            for (int k = 1; k <= A.m; k++)
66
            {
67
                for (int j = 1; j <= m; j++)
68
                    ans.a[i][k] += a[i][j] * A.a[j][k];
69
                if (ans.a[i][k] >= phi)
70
                    ans.a[i][k] = ans.a[i][k] % phi/* + phi*/;
71
            }
72
        return ans;
73
    }
74
    Matrix operator^(const long long &b)
75
    {
76
        long long k = b;
77
        Matrix ans(n, m);
78
        for (int i = 1; i <= n; i++)
79
        {
80
            ans.a[i][i] = 1;
81
        }
82
        Matrix A = *this;
83
        while (k)
84
        {
85
            if (k & 1)
86
                ans = ans * A;
87
            k >>= 1;
88
            A = A * A;
89
        }
90
        return ans;
91
    }
92
};
93
long long pow_mod(long long a, long long b, long long mod)
94
{
95
    long long ans = 1;
96
    while (b)
97
    {
98
        if (b & 1)
99
            ans = ans * a % mod;
100
        b >>= 1;
101
        a = a * a % mod;
102
    }
103
    return ans;
104
}
105
int main()
106
{
107
    freopen("password.in", "r", stdin);
108
    freopen("password.out", "w", stdout);
109
    long long m, p;
110
    Get_Prime();
111
    Matrix O(2, 2);
112
    O.a[1][1] = O.a[1][2] = O.a[2][1] = 1;
113
    Matrix L(2, 1);
114
    L.a[1][1] = 1;
115
    scanf("%lld%lld", &m, &p);
116
    while (m--)
117
    {
118
        long long n, q;
119
        scanf("%lld%lld", &n, &q);
120
        if (q == 1)
121
        {
122
            printf("0\n");
123
            continue;
124
        }
125
        int t = p - q;
126
        if (t == 1)
127
        {
128
            printf("1\n");
129
            continue;
130
        }
131
        phi = Get_Phi(q);
132
        printf("%lld\n", pow_mod(p, ((O ^ n) * L).a[2][1], q));
133
    }
134
}