ZHOJ_#20952. 最大公约数_数论

ZHOJ_#20952. 最大公约数_数论

#20952. 最大公约数

• ID: 20952传统题1000ms256MiB上传者:ZHtwinkle

Description

给定斐波那契数列 FF ,F_1=1，F_2=1，F_i=F_{i-1}+F_{i-2}（i\geq3）F1​=1，F2​=1，Fi​=Fi−1​+Fi−2​（i≥3），随后给出 nn 个询问（1\leq n\leq10^51≤n≤105）

每个询问给定一组 x,yx,y，在一行内输出 F[x]F[x] 和 F[y]F[y] 的最大公约数（1\leq x\leq10^{18}，1\leq y \leq 801≤x≤1018，1≤y≤80）

Format

Input

第一行为一个整数 nn

随后 nn 行，每行两个整数 x,yx,y

Output

输出 nn 行，每行一个整数

Samples

输入数据 1

2
2 3
3 6

Copy

输出数据 1

1
2

Copy

Limitation

1s, 1024KiB for each test case.

斐波那契数列最大公约数定理: gcd( f[a],f[b] )=f[ gcd( a,b ) ]
 

// 估计规模 
#include
using namespace std;
 
const int N=111;
// int f[N+5];				// 46
// long long f[N+5];		// 92	( y<=80 ) 
unsigned long long f[N+5];	// 111
 
void init()
{
    f[1]=f[2]=1;
    
    int i;
    for( i=3;i<=N;i++ )
    {
        f[i]=f[i-1]+f[i-2];
        if( f[i]<0 ) break;
    }
    cout<-1<
}
 
int main()
{   
    init();
 
    return 0;
}

// ZHOJ_#20952. 最大公约数_数论
#include
using namespace std;
#define int long long
 
const int N=88;
int f[N+5];
 
void init()
{
    f[1]=f[2]=1;
    for( int i=3;i<=N;i++ )
        f[i]=f[i-1]+f[i-2];
}
 
inline int gcd( int a,int b ) { return ( a%b==0 ) ? b : gcd( b,a%b ); }
 
signed main()
{
    int n,x,y,i;
 
    init();
 
    scanf("%lld",&n );
    while( n-- )
    {
        scanf("%lld%lld",&x,&y );
        printf("%lld\n",f[ gcd( x,y ) ] );
    }
 
    return 0;
}