如果我们求出Pell方程的最小正整数解后，就可以根据递推式求出所有的解。
则根据上式我们可以构造矩阵，然后就可以快速幂了。
这样就可以求出第k大的解。
HDU3292题就要用到上面的矩阵方法求第k大的解。
题意：求方程x^2-N*y^2=1的最小正整数解。本题要用到高精度，所以用Java。
- import java.math.BigInteger;
- import java.util.Scanner;
- public class Main
- {
- public static void solve(int n)
- {
- BigInteger N, p1, p2, q1, q2, a0, a1, a2, g1, g2, h1, h2,p,q;
- g1 = q2 = p1 = BigInteger.ZERO;
- h1 = q1 = p2 = BigInteger.ONE;
- a0 = a1 = BigInteger.valueOf((int)Math.sqrt(1.0*n));
- BigInteger ans=a0.multiply(a0);
- if(ans.equals(BigInteger.valueOf(n)))
- {
- System.out.println("No solution!");
- return;
- }
- N = BigInteger.valueOf(n);
- while (true)
- {
- g2 = a1.multiply(h1).subtract(g1);
- h2 = N.subtract(g2.pow(2)).divide(h1);
- a2 = g2.add(a0).divide(h2);
- p = a1.multiply(p2).add(p1);
- q = a1.multiply(q2).add(q1);
- if (p.pow(2).subtract(N.multiply(q.pow(2))).compareTo(BigInteger.ONE) == 0) break;
- g1 = g2;h1 = h2;a1 = a2;
- p1 = p2;p2 = p;
- q1 = q2;q2 = q;
- }
- System.out.println(p+" "+q);
- }
- public static void main(String[] args)
- {
- Scanner cin = new Scanner(System.in);
- while(cin.hasNextInt())
- {
- solve(cin.nextInt());
- }
- }
- }