Smith's Problem POJ - 2427 【连分数求最小正整数解】

Smith's Problem POJ - 2427 【连分数求最小正整数解】

题意：求      的最小解。其实x取到最小的时候,y也取到最小。 双曲线画一画啦。

思路：

连分数法求，推荐一个博客https://blog.csdn.net/wh2124335/article/details/8871535?locationNum=14&fps=1

import java.io.*;
import java.util.*;

import java.math.*;


public class Main {
	static long [] a = new long [1000];
	static BigInteger x;
	static BigInteger y;
	public static void  main(String []args) {
		Scanner in=new Scanner(System.in);
		long n;
		while(in.hasNext()) {
			n=in.nextLong();
			if(pell_solution(n)) {
				System.out.println(x+" "+y);
			}
			else
				System.out.println("No solution!");
		}
	}
	
	public static boolean pell_solution(long D){
		double sq=Math.sqrt((double)D);
		long m=(long) Math.floor(sq);
		int i=0;
		if(m*m==D)return false;
		a[i++]=m;
		long b=m,c=1;
		double tmp;
		do{
			c=(D-b*b)/c;
			tmp=(sq+b)/c;
			a[i++]=(long)(Math.floor(tmp));
			b=a[i-1]*c-b;
		}while(a[i-1]!=2*a[0]);
		BigInteger p=new BigInteger("1");
		BigInteger q=new BigInteger("0");
		BigInteger t;
		for(int j=i-2;j>=0;j--){
			t=p;
			p=q.add(p.multiply(BigInteger.valueOf(a[j])));
			q=t;
		}
		if((i-1)%2==0){
			x=p;y=q;
		}else{
			x=BigInteger.valueOf(2).multiply(p).multiply(p).add(BigInteger.ONE);
			y=BigInteger.valueOf(2).multiply(p).multiply(q);
		}
		return true;
	}
}