暑假牛客多校第二场 2023-7-21

dkdklcx / 2023-07-22 / 原文

未补完

E. Square

算法：二分

做法：我们依据x来枚举k，得到 \(x * 10^k\) ，用二分在[0, 1e9]查找mid的平方值，且这个值是第一个大于等于 \(x * 10^k\) 的值。得到这个值后我们再判断这个值在除 \(10^k\) 后是否与 \(x\) 相等即可。

code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

int getlen(LL x)
{
    int cnt = 0;
    while(x)x /= 10, cnt++;
    return cnt;
}

LL sl(LL x)
{
    LL l = 0, r = 1e9;
    while(l < r)
    {
        LL mid = (l + r) / 2;
        if(mid * mid >= x)r = mid;
        else l = mid + 1;
    }
    return l;
}

LL sr(LL x)
{
    LL l = 0, r = 1e9;
    while(l < r)
    {
        LL mid = (l + r + 1) / 2;
        if(mid * mid <= x)l = mid;
        else r = mid - 1;
    }
    return r;
}

void solve()
{
    LL x;
	cin >> x;
	if(x == 0)
    {
        cout << 0 << endl;
        return;
    }

    int len = getlen(x);
    for(int k = 0; k <= 19 - len ; k++)
    {
        LL p = 1;
        for(int i = 1; i <= k ; i++)p = p * 10;

        LL l = sl(x * p);

        LL f = l * l;
        for(int j = 1; j <= k ; j++)f /= 10;
        if(f == x)
        {
            cout << l << endl;
            return;
        }
    }
    cout << "-1" << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}