首页 > 专题系列 > Java解POJ > POJ 2427 Smith’s Problem [解题报告] Java
2013
11-11

POJ 2427 Smith’s Problem [解题报告] Java

Smith’s Problem

问题描述 :

Computer has greatly released scientists from heavy calculation. Before computer is invented, calculation must be done by hand, which is boring and easy to make mistake. But now, with the help of computer much calculation can be finished within a second.

But one day Professor Smith met a strange problem. He had tried to find the positive solutions of the equation with the following form:

X ^ 2 – N * Y ^ 2 = 1,


in which N is a positive integer. But for many values of N, his poor computer seems cannot find an answer!

“That’s strange!” said Professor Smith “There must be something wrong with my program!” And you, the assistant of Professor Smith, are assigned the work to solve the problem.

输入:

The input will contain several test cases; each contains a positive integer N (1 <= N <= 10 ^ 8) in a single line.

输出:

For each test case, in a line output two positive integers X and Y that satisfy the equation and are smaller than 10 ^ 1000. If there is no such solution, output “No solution!”

样例输入:

52
256
991

样例输出:

649 90
No solution!
379516400906811930638014896080 12055735790331359447442538767

解题代码:

//* @author 
import java.util.*;
import java.math.*;
public class Main {
 static BigInteger p1,p2,p3,q1,q2,q3,a1,a2,a0,h1,h2,g1,g2,p,q;
 static int nn;
 static void solve(){
  p2=BigInteger.ONE; p1=BigInteger.ZERO;
  q2=BigInteger.ZERO; q1=BigInteger.ONE;
  a1=BigInteger.valueOf((long)Math.sqrt(nn));
  a0=BigInteger.valueOf((long)Math.sqrt(nn));
  g1=BigInteger.ZERO;h1=BigInteger.ONE;
  BigInteger n0=BigInteger.valueOf(nn);
  while(true){
   g2=a1.multiply(h1).subtract(g1);
   h2=(n0.subtract(g2.multiply(g2))).divide(h1);
   a2=g2.add(a0).divide(h2);
   p=p2.multiply(a1).add(p1);
   q=q2.multiply(a1).add(q1);
   if(p.multiply(p).subtract(n0.multiply(q.multiply(q))).compareTo(BigInteger.ONE)==0)
     return ;
   a1=a2;
   g1=g2;
   h1=h2;
   p1=p2;p2=p;
   q1=q2;q2=q;
   }
 }

 public static void main(String[] args) {
   Scanner in=new Scanner(System.in);
   while(in.hasNext()){
    nn=in.nextInt();
    int t=(int)Math.sqrt(nn);
    if(t*t==nn)
      System.out.println("No solution!");
    else{
      solve();
      System.out.println(p+" "+q);
     }
  }
 }


}