【HDU】5778 - abs（思维）

FishWang

发布于 2025-08-27 09:45:00

6900

代码可运行

运行总次数：0

代码可运行

点击打开题目

abs

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1359 Accepted Submission(s): 477

Problem Description

Given a number x, ask positive integer , that satisfy the following conditions: 1. The absolute value of y - x is minimal 2. To prime factors decomposition of Y, every element factor appears two times exactly.

Input

The first line of input is an integer T ( ) For each test case，the single line contains, an integer x ( )

Output

For each testcase print the absolute value of y - x

Sample Input

Sample Output

Source

BestCoder Round #85

妈呀好紧张，bc结束之前5分钟AC了。

他要每个质因数个数都为2，那么开一下根号，就是说这个数质因数个数都为1，写一个函数就行了。

把最初的 n 开根号得 t ，如果 t * t == n 而且 t 不满足条件的话，那么分别从 t 的两边找，如果 t * t < n ，那么从 t + i 和 t - i + 1找（ i 从 0 开始）。

代码如下：（刚开始总是wa，小情况考虑不到，所以代码比较复杂，思路还是清楚的）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
bool check(__int64 x)
{
    if (x == 1)
        return false;
    for (int i = 2 ; i <= sqrt(x) ; i++)
    {
        if (x % i == 0)
        {
            x /= i;
            if (x % i == 0)
                return false;
        }
    }
    return true;
}
int main()
{
    int u;
    __int64 n;
    __int64 res;
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%I64d",&n);
        if (n == 1)
        {
            printf ("3\n");
            continue;
        }
        __int64 ans = sqrt(n);
        if (check(ans) && ans * ans == n)
        {
            printf ("0\n");
            continue;
        }
        if (ans * ans != n)
        {
            for (int i = 1 ; ; i++)
            {
                __int64 t1 = 0,t2 = 0;
                if (check(ans+i))
                {
                    res = (ans+i)*(ans+i);
                    res -= n;
                    t1 = abs(res);
                }
                if (check(ans-i+1))
                {
                    res = (ans-i+1)*(ans-i+1);
                    res -= n;
                    t2 = abs(res);
                }
                if (t1 && t2)
                {
                    res = min (t1,t2);
                    break;
                }
                else if (t1 || t2)
                {
                    res = max (t1,t2);
                    break;
                }
            }
        }
        else
        {
            for (int i = 0 ; ; i++)
            {
                __int64 t1 = 0,t2 = 0;
                if (check(ans+i))
                {
                    res = (ans+i)*(ans+i);
                    res -= n;
                    t1 = abs(res);
                }
                if (check(ans-i))
                {
                    res = (ans-i)*(ans-i);
                    res -= n;
                    t2 = abs(res);
                }
                if (t1 && t2)
                {
                    res = min (t1,t2);
                    break;
                }
                else if (t1 || t2)
                {
                    res = max (t1,t2);
                    break;
                }
            }
        }
        printf ("%I64d\n",abs(res));
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

int