ACM – UVa10023 – 开平方 -

本题目计算开根号数字，给出Y求X。X = sqrt(Y)，主要问题在Y的超大数据。

时间限制是3s。我使用的大数模板中没有一个大数除大数的算法，因此直接借用Java来搞一搞。

利用公式$$(5/x+x)/2 = x$$递归逼近求解。这个公式比较好推，移项即可。

import java.util.*;
import java.math.*;
import java.util.HashSet;
public class Main {
    static Set set;
    public static BigInteger cal(BigInteger a, BigInteger b) {
        BigInteger ans = (a.divide(b) .add(b)).divide(new BigInteger("2"));
        if(set.contains(ans))
            return ans;
        else {
            set.add(ans);
            return cal(a, ans);
        }
    }
    public static void main(String [] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger a;
        String s;
        int T = cin.nextInt();
        while(T-- != ) {
            set = new HashSet();
            s = cin.next();
            a = new BigInteger(s);
            System.out.println(cal(a, a));
            if(T != )
            System.out.println();
        }
    }
}

参考他人代码，不需要用set，直接判断是否和前一个相等即可= =。

再一个就是模拟手算。手算法有些麻烦。。注意第二个除数开始余数*20即可。