连分数求解Pell方程

如果我们求出Pell方程的最小正整数解后，就可以根据递推式求出所有的解。

则根据上式我们可以构造矩阵，然后就可以快速幂了。

这样就可以求出第k大的解。

HDU3292题就要用到上面的矩阵方法求第k大的解。

拓展一点：

(1)如果第n个三角数t等于m的平方，即，那么x=2n+1，y=m，就是丢番图方程的解。

(2)求丢番图方程的最小正整数解，其中d为非完全平方数的正整数。

题目：http://poj.org/problem?id=2427

题意：求方程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());   }}  
}  

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2281

题意：给出一个数N，求1到N的范围内，找到一个最大的n，满足，N最大达到10^18

分析：我们把上式写成，然后就是解Pell方程即可。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！