华中农业大学第五届程序设计大赛网络同步赛-D

Problem D: GCD

Time Limit: 1 Sec Memory Limit: 1280 MB
Submit: 179 Solved: 25
[Submit][Status][Web Board]

Description

XiaoMingfoundthecomputetimeof

Input

The first line is an positive integer T. (

Output

In each test case, output the compute result of

Sample Input

1 
1 2 3

Sample Output

HINT

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #define LL long long
 6 #define MAXN 100
 7 
 8 using namespace std;
 9 
10 int MOD;
11 
12 struct Matrix  
13 {  
14     LL a[MAXN][MAXN];  
15     int r, c; 
16 };  
17 
18 Matrix ori, res; 
19 
20 void init()  
21 {  
22     memset(res.a, 0, sizeof(res.a));  
23     res.r = 2; res.c = 2;  
24     for(int i = 1; i <= 2; i++)  
25         res.a[i][i] = 1;  
26     ori.r = 2; ori.c = 2;  
27     ori.a[1][1] = ori.a[1][2] = ori.a[2][1] = 1;  
28     ori.a[2][2] = 0;  
29 }  
30 
31 Matrix multi(Matrix x, Matrix y)  
32 {  
33     Matrix z;  
34     memset(z.a, 0, sizeof(z.a));  
35     z.r = x.r, z.c = y.c;    
36     for(int i = 1; i <= x.r; i++) 
37     {  
38         for(int k = 1; k <= x.c; k++)      
39         {  
40             if(x.a[i][k] == 0) continue;
41             for(int j = 1; j<= y.c; j++)  
42                 z.a[i][j] = (z.a[i][j] + (x.a[i][k] * y.a[k][j]) % MOD) % MOD;  
43         }  
44     }  
45     return z;  
46 }  
47 void Matrix_mod(int n)  
48 {  
49     while(n)  
50     {  
51         if(n & 1)  
52             res = multi(ori, res);  
53         ori = multi(ori, ori);  
54         n >>= 1;  
55     }  
56     printf("%lld
", res.a[1][2] % MOD);  
57 }  
58 
59 int main()
60 {
61     int T, n, m;
62     scanf("%d", &T);
63     while(T--)
64     {
65         scanf("%d%d%d", &n, &m, &MOD);
66         LL pos = __gcd(n+2, m+2);
67         init();
68         Matrix_mod(pos);
69     }
70     return 0;
71 }