P1306 斐波那契公约数

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
inline int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < ‘0‘ || ch > ‘9‘)
    {
        if(ch == ‘-‘) op = -1;
        ch = getchar();
    }
    while(ch >= ‘0‘ && ch <= ‘9‘)
    {
        (ans *= 10) += ch - ‘0‘;
        ch = getchar();
    }
    return ans * op;
}
typedef int mainint;
#define int long long
const int mod = 19990208;
struct mat
{
    int a[3][3];
    int r,c;
    inline void mem() { memset(a,0,sizeof(a)); r = 0,c = 0; }
};
int n,m;
mat mul(mat x,mat y)
{
    mat p; p.mem();
    for(int i = 0;i < x.r;i++)
        for(int j = 0;j < y.c;j++)
            for(int k = 0;k < x.c;k++)
                (p.a[i][j] += x.a[i][k] * y.a[k][j]) %= mod;
    p.r = x.r,p.c = y.c;
    return p;
}
void power(int b)
{
    mat ans,res;
    ans.mem(),res.mem();
    res.r = res.c = 2;
    res.a[0][0] = res.a[0][1] = res.a[1][0] = 1;
    ans.r = 1,ans.c = 2;
    ans.a[0][0] = ans.a[0][1] = 1;
    while(b)
    {
        if(b & 1) ans = mul(ans,res);
        res = mul(res,res);
        b >>= 1;
    }
    printf("%lld\n",ans.a[0][0]);
}
int gcd(int x,int y) { return !y ? x : gcd(y,x % y); }
mainint main()
{
    int t = read();
    while(t--)
    {
        int n = read(),m = read();
        n = gcd(n,m);
        if(n <= 2) printf("1\n");
        else power(n - 2);
    }
}