2087: 最大公约数

    刚刚上完小学四年级的Gy和Nsk在讨论有关用辗转相除法求最大公约数的问题。他们想知道，对于求GCD(a,b) (a<=b<=N)，辗转最多的一对是哪一对。

    辗转次数的定义：对于数对A,B(A<=B)，令A'=B mod A,B'=A，每次将(A,B)变为(A',B')，直到最终A'=gcd(A,B)时总共进行的变换次数。

    辗转次数的具体解释：

    比如在N=10时

    4,6 -> 2,4 ==> 2

     GCD(4,6)是2

     辗转了1次

    3,8 -> 2,3 -> 1,2 ==> 1

     GCD(3,8)是1

     辗转了2次

    2,9 -> 1,2 ==> 1

     GCD(2,9)是1

     辗转了1次

    所以(3,8)比(2,9)和(4,6)辗转的多。

    一行，包含一个整数N，含义如题所述。

    两行各一个整数，分别表示辗转次数最多的数对的a和b。

    如果辗转次数一样，取b最小的（如果b也一样，取a最小的）。

4

2
3