POJ 3175 Finding Bovine Roots （暴力求解）

题意：给定一串数字，问你这是一个数字开方根得到的前几位，问你是哪个数字。析：如果 x.123... 这个数字的平方是一个整数的话，那必然sqr(x.124) > ceil(sqr(x.123)) [sqr = 求平方, ceil = 向上取整
所以，就可以从小到大枚举它的整数部分 x ，遇到第一个满足结果的 x，就是答案了。

开始时，我从1开始暴力超时了。。

代码如下：

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <string>

#include <algorithm>

#include <vector>

#include <map>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f3f;

const double eps = 1e-11;

const int maxn = 1000 + 5;

const int dr[] = {0, 0, -1, 1};

const int dc[] = {-1, 1, 0, 0};

int main(){

    int n;

    double x;

    scanf("%d", &n);

    scanf("%lf", &x);

    double t = 1.0;

    for(int i = 0; i < n; ++i)

        t /= 10.0;

    x *= t;

    for(int i = 1; ;++i){

        double y = (LL)((x+i) * (i+x)) + 1;

        double yy = (x+t+i) * (x+t+i);

        if(yy > y){

            printf("%lld\n", (LL)(y));

            break;

        }

    }

    return 0;

}

巴特西

POJ 3175 Finding Bovine Roots （暴力求解）

最新文章

热门文章