給出N,e,d，3<=e<31,求出p,q;
二分給BigInteger開方很好用。
另外就是枚舉(p-1)*(q-1)在比賽的時候也不失為一種很不錯的方法。
import java.math.*;
import java.util.*;
import java.io.*;
public class Main
{
public static BigInteger Sqrt(BigInteger x)
{
BigInteger l=new BigInteger("0");
BigInteger r=x;
while(l.compareTo(r)<0)
{
BigInteger mid=l.add(r).divide(BigInteger.valueOf(2));
if(mid.multiply(mid).compareTo(x)<0)
l=mid.add(BigInteger.ONE);
else if(mid.multiply(mid).compareTo(x)==0)
return mid;
else
r=mid.subtract(BigInteger.ONE);
}
return l;
}
public static boolean Judge(BigInteger x)
{
BigInteger tem=new BigInteger("0");
tem=Sqrt(x);
if(tem.multiply(tem).compareTo(x)==0)
return true;
else
return false;
}
public static void main(String[] args)
{
Scanner cin = new Scanner (new BufferedInputStream(System.in));
String sn;
String se;
String sd;
int ca=0;
while(true)
{
ca++;
sn=cin.next();
se=cin.next();
sd=cin.next();
BigInteger n=new BigInteger(sn);
BigInteger e=new BigInteger(se);
BigInteger d=new BigInteger(sd);
if(n.compareTo(BigInteger.ZERO)==0 && e.compareTo(BigInteger.ZERO)==0 &&d.compareTo(BigInteger.ZERO)==0)
break;
for(int i=1;i<=100;i++)
{
BigInteger t=e.multiply(d).subtract(BigInteger.ONE).divide(BigInteger.valueOf(i));
BigInteger t2= t.subtract(n).subtract(BigInteger.ONE).pow(2).subtract(BigInteger.valueOf(4).multiply(n));
if(Judge( t2 )==true)
{
t2=Sqrt(t2);
// System.out.println(t2);
BigInteger p=n.subtract(t).add(BigInteger.ONE).add(t2).divide(BigInteger.valueOf(2));
BigInteger q=n.subtract(t).add(BigInteger.ONE).subtract(t2).divide(BigInteger.valueOf(2));
if(q.compareTo(p)<0)
{
BigInteger mm=q;
q=p;
p=mm;
}
System.out.println("Case #"+ca+":"+" "+p+" "+q);
break;
}
}
}
}
}