UVa 10023 Square root：高精度及开平方公式

UVa 10023 Square root：高精度及开平方公式2014-07-22 csdn博客 synapse710023 - Square root

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=964

The Problem

You are to determinate X by given Y, from expression

The Input

The first line is the number of test cases, followed by a blank line.

Each test case of the input contains a positive integer Y （1<=Y<=101000）, with no blanks or leading zeroes in it.

It is guaranteed, that for given Y, X will be always an integer.

Each test case will be separated by a single line.

The Output

For each test case, your program should print X in the same format as Y was given in input.

Print a blank line between the outputs for two consecutive test cases.

Sample Input

7206604678144

Sample Output

2684512

使用开平方公式可破，牛顿法居然会TLE..（Java差点TLE）

完整代码：

/*0.562s*/#include <cstdio>#include <cstring>const int MAXN = 1010;char s[MAXN], re[MAXN];int big（char s1[], char s2[]）{int len1, len2, i, q;q = 0;while （s1[q] == "0"） q++;strcpy（s1, s1 + q）;if （strlen（s1） == 0）{s1[0] = "0";s1[1] = 0;}q = 0;while （s2[q] == "0"） q++;strcpy（s2, s2 + q）;if （strlen（s2） == 0）{s2[0] = "0";s2[1] = 0;}len1 = strlen（s1）;len2 = strlen（s2）;if （len1 > len2）return 1;else if （len1 < len2）return 0;else{for （i = 0; i < len1; i++）{if （s1[i] > s2[i]）return 1;else if （s1[i] < s2[i]）return 0;}}return 0;}void mul（char s[], int t, char re[]） //乘{int left, i, j, k, len;char c;left = 0;j = 0;for （i = strlen（s） - 1; i >= 0; i--）{k = t * （s[i] - "0"） + left;re[j++] = （k % 10） + "0";left = k / 10;}while （left > 0）{re[j++] = （left % 10） + "0";left /= 10;}re[j] = 0;len = strlen（re）;for （i = 0; i < len / 2; i++）{c = re[i];re[i] = re[len - 1 - i];re[len - 1 - i] = c;}return;}void sub（char a[], char b[]）//减{int left, len1, len2, temp, j;len1 = strlen（a） - 1;len2 = strlen（b） - 1;left = 0;while （len2 >= 0）{temp = a[len1] - b[len2] + left;if （temp < 0）{temp += 10;left = -1;}elseleft = 0;a[len1] = temp + "0";len1--;len2--;}while （len1 >= 0）{temp = a[len1] - "0" + left;if （temp < 0）{temp += 10;left = -1;}elseleft = 0;a[len1] = temp + "0";len1--;}j = 0;while （a[j] == "0"） j++;strcpy（a, a + j）;if （strlen（a） == 0）{a[0] = "0";a[1] = 0;}return;}void sqr（char s[], char re[]）//开方{char temp[MAXN];char left[MAXN];char p[MAXN];int i, j, len1, len2, q;len1 = strlen（s）;if （len1 % 2 == 0）{left[0] = s[0];left[1] = s[1];left[2] = 0;j = 2;}else{left[0] = s[0];left[1] = 0;j = 1;}re[0] = "0";re[1] = 0;q = 0;while （j <= len1）{mul（re, 20, temp）;len2 = strlen（temp）;for （i = 9; i >= 0; i--）{temp[len2 - 1] = i + "0";mul（temp, i, p）;if （！big（p, left））break;}re[q++] = i + "0";re[q] = 0;sub（left, p）;len2 = strlen（left）;left[len2] = s[j];left[len2 + 1] = s[j + 1];left[len2 + 2] = 0;j += 2;}}int main（void）{int t;scanf（"%d", &t）;while （t--）{scanf（"%s", s）;sqr（s, re）;int i = 0;while （re[i] == "0"） i++;strcpy（re, re + i）;printf（"%s
", re）;if （t） putchar（"
"）;}return 0;}

/*2.818s*/import java.io.*;import java.util.*;import java.math.*;public class Main {static final BigInteger TWO = new BigInteger（"2"）;static Scanner cin = new Scanner（new BufferedInputStream（System.in））;public static void main（String[] args） {int n = cin.nextInt（）;while （n-- > 0） {BigInteger y = cin.nextBigInteger（）;BigInteger c = y, temp;do {temp = y;y = temp.add（c.divide（y））.divide（TWO）;}while （y.compareTo（temp） == -1）;System.out.println（y）;if （n > 0）System.out.println（）;}}}