HDU-5973ウィゾフゲーム+大数

1832 ワード

タイトル
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();
    }
}