四月の诈尸笔记

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn = 4;
 7 LL mod;
 8 
 9 struct Matrix
10 {
11     LL m[maxn][maxn];
12     Matrix(){memset(m, 0, sizeof(m));}
13     void E(){for(int i = 0; i < maxn; i++) m[i][i] = 1;}
14 };
15 
16 Matrix M_mul(Matrix a, Matrix b)
17 {
18     Matrix ret;
19     for(int i = 0; i < maxn; i++)
20         for(int j = 0; j < maxn; j++)
21             for(int k = 0; k < maxn; k++)
22                 ret.m[i][j] = ( ret.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod ) % mod;
23     return ret;
24 }
25 
26 Matrix M_qpow(Matrix P, LL n)
27 {
28     Matrix ret;
29     ret.E();
30     while(n)
31     {
32         if(n & 1LL) ret = M_mul(ret, P);
33         n >>= 1LL;
34         P = M_mul(P, P);
35     }
36     return ret;
37 }
38 
39 LL qpow(LL a, LL b)
40 {
41     LL ret = 1LL;
42     while(b)
43     {
44         if(b & 1LL) ret = ret * a % mod;
45         a = a * a % mod;
46         b >>= 1LL;
47     }
48     return ret;
49 }
50 
51 int main(void)
52 {
53     int T;
54     scanf("%d", &T);
55     while(T--)
56     {
57         LL n, a, b, c, p;
58         cin >> n >> a >> b >> c >> p;
59         if(a % p == 0) puts("0");
60         else
61         {
62             Matrix A, B;
63             A.m[1][1] = A.m[2][3] = A.m[3][1] = A.m[3][2] = 1LL;
64             A.m[3][3] = c;
65             mod = p - 1LL;
66             B = M_qpow(A, n - 1LL);
67             LL e = b * (B.m[2][1] + B.m[2][3]) % mod;
68             mod = p;
69             LL ans = qpow(a, e);
70             cout << ans << endl;
71         }
72     }
73     return 0;
74 }