题目链接：

题意：给出方程x^2-n*y^2=1的最小整数解。

思路：参见金斌大牛的论文《欧几里得算法的应用》。

 

import java.util.*;import java.math.*;import java.io.*;public class Main {       static BigInteger ONE=BigInteger.valueOf(1);    static BigInteger ZERO=BigInteger.valueOf(0);        public static BigInteger V(int x)    {        return BigInteger.valueOf(x);    }    public static void main(String[] args) {        Scanner S=new Scanner(System.in);        int T;        T=S.nextInt();        while(T--!=0)        {            BigInteger p0,p1,p2,q0,q1,q2,g0,g1,h0,h1,a,a0,n;            n=S.nextBigInteger();            p0=ZERO; p1=ONE;            q0=ONE; q1=ZERO;            a0=a=V((int)Math.sqrt(n.intValue()));            g0=ZERO; h0=ONE;            while(true)            {                g1=ZERO.subtract(g0).add(a.multiply(h0));                h1=n.subtract(g1.multiply(g1)).divide(h0);                p2=a.multiply(p1).add(p0);                q2=a.multiply(q1).add(q0);                a=g1.add(a0).divide(h1);                if(p2.multiply(p2).subtract(n.multiply(q2).multiply(q2)).compareTo(ONE)==0)                {                    break;                }                p0=p1; p1=p2;                q0=q1; q1=q2;                g0=g1; h0=h1;            }            System.out.print(p2);            System.out.print(' ');            System.out.println(q2);        }    }}