[原创]华中农业大学第五届程序设计大赛 D GCD [fibonacci+矩阵乘法]【数学】

2017-05-26 21:26:18 Tabris_ 阅读数：409

博客爬取于2020-06-14 22:40:35
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72773724

题目链接:http://acm.hzau.edu.cn/problem.php?id=1202
————————————————————————————————————————
1202: GCD
Time Limit: 1 Sec Memory Limit: 1280 MB
Submit: 241 Solved: 44
[Submit][Status][Web Board]
Description
这里写图片描述
Input
The first line is an positive integer T . (1<=T<= 10^3) indicates the number of test cases. In the next T lines, there are three positive integer n, m, p (1<= n,m,p<=10^9) at each line.

Output
这里写图片描述

Sample Input
1
1 2 3

Sample Output
1

————————————————————————————————————————
题目大意：
就是让你求gcd（1+sumn,1+summ）gcd（1+sum_n,1+sum_m）%p

解题方法：
问什么叫方法，因为暴力啊。。。

首先暴力的打了一个1+sumn1+sum_n的表,然后惊奇的发现这就是fibonacci数列

然后就变成了gcd（fibn+2,fibm+2）gcd（fib_{n+2},fib_{m+2}）%p

然后根据fibonacci数列的性质

gcd（fibn+2,fibm+2）=fib(gcd（n+2,m+2）)gcd（fib_{n+2},fib_{m+2}）\\ = fib( gcd（n+2,m+2）)

所以同一个矩阵乘法就可以了

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 2e5+7;
//const int INF = (~(1<<31));

int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9') ch = getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch = getchar();}
    return x;
}
/*******************************************/
int n,m,MOD;
const int M = 2;
struct Matrix{
    LL m[M][M];
    void clear0(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=0;
    }
    void clearE(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=(i==j);
    }
};

Matrix operator *(Matrix &a,Matrix &b){
    Matrix c;c.clear0();

    for(int k=0;k<M;k++)
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;

    return c;
}

Matrix operator ^(Matrix &a,LL b){
    Matrix c;c.clearE();
    while(b){
        if(b&1) c=c*a;
        b>>=1,a=a*a;
    }
    return c;
}

LL solve(int x){
    Matrix a,b;
    a.m[0][0]=0,a.m[0][1]=1;
    b.m[0][0]=0,b.m[0][1]=1;
    b.m[1][0]=1,b.m[1][1]=1;
    b=b^x;a=a*b;
    return a.m[0][0];
}

int main(){
    int _=read();
    while(_--){
        n=read(),m=read(),MOD=read();
        printf("%lld\n",solve(__gcd(n+2,m+2)));
    }
    return 0;
}