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

10023 - 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

1

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;
        }
        else
            left = 0;
        a[len1] = temp + '0';
        len1--;
        len2--;
    }
    while (len1 >= 0)
    {
        temp = a[len1] - '0' + left;
        if (temp < 0)
        {
            temp += 10;
            left = -1;
        }
        else
            left = 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\n", re);
        if (t) putchar('\n');
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

/*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();
        }
    }
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索close() scanner java
， re
， char
， while
， len
， temp
， left
开平方
10023、mswd 10023演员、mswd 10023 先锋影音、0x10023、mswd10023是av吗，以便于您获取更多的相关知识。