题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=111

题目大意

给出一个自然数X,请找出平方不大于X的最大整数。

题解

二分平方加高精度。超时了,压八位才过。好久没写过高精度了,调试了好几发。

然后我搜到了手动开方的算法,写完之后才发现这个方法行不通,但是代码是对的,也贴在下面。

代码

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 2000, BIT = 8;
long long MOD = 100000000;
long long l[N + 5], r[N + 5], mid[N + 5], tmp[N + 5], ini[N + 5], ans[N + 5];
char s[N + 5];

void Push(long long *a) {
    for (int i = 1; i < a[0]; ++i) {
        a[i + 1] += a[i]/MOD;
        a[i] %= MOD;
    }
    while (a[a[0]] >= MOD) {
        a[a[0] + 1] = a[a[0]]/MOD;
        a[a[0]++] %= MOD;
    }
    return;
}

void Add(long long a[], long long b[], long long *res) {
    res[0] = max(a[0], b[0]);
    for (int i = 1; i <= res[0]; ++i) res[i] = 0;
    for (int i = 1; i <= a[0]; ++i) res[i] += a[i];
    for (int i = 1; i <= b[0]; ++i) res[i] += b[i];
    Push(res);
    return;
}

void Add1(long long *a) {
    ++a[1];
    Push(a);
    return;
}

void Div(long long a[], long long b, long long *res) {
    long long t = 0;
    for (int i = (int)a[0]; i >= 1; --i) {
        res[i] = (t*MOD + a[i])/b;
        t = (t*MOD + a[i]) % b;
    }
    res[0] = a[0];
    while(res[res[0]] == 0 && res[0] > 1) --res[0];
    return;
}

void Mult(long long a[], long long b[], long long *res) {
    res[0] = a[0] + b[0] - 1;
    for (int i = 1; i <= res[0]; ++i) res[i] = 0;
    for (int i = 1; i <= a[0]; ++i)
        for (int j = 1; j <= b[0]; ++j) res[i + j - 1] += a[i]*b[j];
    Push(res);
    return;
}

int Compile(long long a[], long long b[]) {
    if (a[0] > b[0]) return 1;
    if (a[0] < b[0]) return -1;
    for (int i = (int)a[0]; i >= 1; --i) {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return -1;
    }
    return 0;
}

void Equal(long long *a, long long b[]) {
    a[0] = b[0];
    for (int i = 1; i <= a[0]; ++i) a[i] = b[i];
    return;
}

void Input() {
    scanf("%s", s);
    int len = (int)strlen(s);
    for (int i = 0; i < len/2; ++i) swap(s[i], s[len - 1 - i]);
    ini[0] = (len - 1)/BIT + 1;
    for (int i = 1; i <= ini[0]; ++i) {
        ini[i] = 0;
        long long x = MOD;
        for (int j = 1; j <= BIT; ++j) {
            x /= 10;
            if (i*BIT - j < len) ini[i] += (s[i*BIT - j] - '0')*x;
        }
    }
    return;
}

void Print(long long x) {
    if (x/10) Print(x/10);
    printf("%lld", x % 10);
    return;
}

void Output() {
    for (int i = (int)ans[0]; i >= 1; --i) {
        if (i != ans[0]) {
            if (ans[i]/10 == 0) printf("0000000");
            else if (ans[i]/100 == 0) printf("000000");
            else if (ans[i]/1000 == 0) printf("00000");
            else if (ans[i]/10000 == 0) printf("0000");
            else if (ans[i]/100000 == 0) printf("000");
            else if (ans[i]/1000000 == 0) printf("00");
            else if (ans[i]/10000000 == 0) printf("0");
        }
        Print(ans[i]);
    }
    printf("\n");
}

int main() {
    Input();
    l[0] = l[1] = ans[0] = ans[1] = 1;
    for (int i = 0; i <= ini[0]; ++i) r[i] = ini[i];
    while (Compile(l, r) < 0) {
        Add(l, r, tmp);
        Div(tmp, 2, mid);
        Mult(mid, mid, tmp);
        if (Compile(tmp, ini) <= 0) {
            Equal(ans, mid);
            Equal(l, mid);
            Add1(l);
        } else Equal(r, mid);
    }
    Output();
    return 0;
}

手动开方

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 2000;
long long f[N + 5], a[N + 5];
char s[N + 5];

int main() {
    scanf("%s", s);
    int len = (int)strlen(s);
    for (int i = 1; i <= len; ++i) a[i] = s[len - i] - '0';
    long long k = 1, r = 0;
    if (len & 1) r = a[len--];
    else {
        r = a[len]*10 + a[len - 1];
        len -= 2;
    }
    f[k] = floor(sqrt(r));
    r = r - f[k]*f[k];
    long long t = f[k];
    for (int i = len; i > 0; i -= 2) {
        r = r*100 + a[i]*10 + a[i - 1];
        long long q = r/(t*20) + 1, p;
        do {
            --q;
            p = (t*20 + q)*q;
        } while (p > r);
        f[++k] = q;
        r -= p;
        t = t*10 + q;
    }
    for (int i = 1; i <= k; ++i) printf("%lld", f[i]);
    printf("\n");
    return 0;
}

转载保留版权:http://haipz.com/blog/i/6446 - 海胖博客