3049214_ac_827ms_5168k.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 62 行

import java.util.*;
import java.math.*;

public class Main 
{
	public static void main(String[] args) 
	{
		Scanner cin = new Scanner (System.in);
		int c, n, f;
		int a, P, Q;
		boolean succ;
		BigInteger x, y, x1, y1, t;
		
		while(cin.hasNext())
		{
			n = cin.nextInt();
			c = (int)Math.sqrt(n);
			if(c*c==n)
			{
				System.out.println("No solution!");
				continue;
			}
			succ = true;
			f = -1;
			P = c;
			Q = n - P*P;
			x = BigInteger.valueOf(c);
			y = BigInteger.valueOf(1);
			x1 = BigInteger.valueOf(1);
			y1 = BigInteger.valueOf(0);
			while(f*Q!=1)
			{
				if(x.toString().length()>=1000||y.toString().length()>=1000)
				{
					succ = false;
					break;
				}
				a = (c+P)/Q;
				P = a*Q-P;
				Q = (n-P*P)/Q;
				f *= -1;
				t = x;
				x = x.multiply(BigInteger.valueOf(a));
				x = x.add(x1);
				x1 = t;
				t = y;
				y = y.multiply(BigInteger.valueOf(a));
				y = y.add(y1);
				y1 = t;
			}
			if(!succ)
			{
				System.out.println("No solution!");
			}
			else
			{
				System.out.println(x+" "+y);
			}
		}
	}
}