HDU-5973ウィゾフゲーム+大数
1832 ワード
タイトル
Game of Taking Stones
問題解
大数版のウィゾフゲームは、javaで簡単に書きますが、javaにも高精度の開方関数はなく、ニュートン反復を書いて根を下ろします.
コード#コード#
Game of Taking Stones
問題解
大数版のウィゾフゲームは、javaで簡単に書きますが、javaにも高精度の開方関数はなく、ニュートン反復を書いて根を下ろします.
コード#コード#
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.Scanner;
public class Main {
static BigDecimal sqrt(BigDecimal num, int scale){ //x^2 = num
BigDecimal x1 = new BigDecimal(1);
BigDecimal x2;
BigDecimal dif;
BigDecimal precision =x1.divide(new BigDecimal(10).pow(100));
while(true){
x2 = x1.subtract(x1.pow(2).subtract(num).divide(x1.multiply(num),scale, BigDecimal.ROUND_HALF_EVEN));
if(x1.compareTo(x2) > 0){
dif = x1.subtract(x2);
}else{
dif = x2.subtract(x1);
}
if(dif.compareTo(precision) < 0){
break;
}
x1 = x2;
}
return x1;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
MathContext mc = new MathContext(105,RoundingMode.HALF_UP);
BigDecimal x = sqrt(new BigDecimal(5),105);
x = x.add(new BigDecimal("1"),mc);
x = x.divide(new BigDecimal("2"),mc);
while(in.hasNext()){
BigDecimal A = in.nextBigDecimal();
BigDecimal B = in.nextBigDecimal();
BigDecimal C;
if(A.compareTo(B) > 0){
C = B;
B = A;
A = C;
}
B = B.subtract(A);
B = B.multiply(x);
B = B.setScale(0, RoundingMode.FLOOR);
if(B.equals(A))
System.out.println("0");
else
System.out.println("1");
}
in.close();
}
}