问题 : GCD

时间限制: 1 Sec  

内存限制: 1280 MB

题目描述

输入

 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.

输出

样例输入

1 1 2 3

样例输出

1

提示

gcd(1 + Sn, 1 + Sm) = gcd(fib(n + 2), fib(m + 2)) = fib(gcd(n + 2, m + 2)).

#include 
     
      int gcd(int a, int b){    return b ? gcd(b, a % b) : a;}int main(){    int t, n, m, p, s, a, b, c;    scanf("%d", &t);    while (t--)    {        scanf("%d%d%d", &n, &m, &p);        s = gcd(n + 2, m + 2);        a = 1;b = 1;c = 1;        for (int i = 3; i <= s; i++)        {            c = (a + b) % p;            a = b;            b = c;        }        printf("%d\n", c);    }    return 0;}