981      技術社區[雲棲]

POJ 2427 pell方程

題意：求解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());   
        }
    }  
}  

最後更新：2017-04-03 16:48:47

  上一篇： Javascript頁麵打印的頁眉頁腳的清除與設置

  下一篇： USB充電插拔和usb Debugging connect提示