HDU 5778 abs (week2-XDUACM)_given a number x, ask positive integer y≥2, that s-CSDN博客

本文链接：https://blog.csdn.net/coderDogg/article/details/80333850

本文探讨了一道算法题目，给定整数x，寻找符合条件的整数y，即y的所有质因数出现次数为0或2次，同时使得y-x的绝对值尽可能小。通过分析，提出了一种有效的方法来解决此问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

abs

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

Problem Description

Given a number x, ask positive integer

y≥2, 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 (

1≤T≤50)
For each test case，the single line contains, an integer x (

1≤x≤1018)

Output

For each testcase print the absolute value of y - x

Sample Input

Sample Output

题意：给出一个x，求出一个y满足y的所有质因数出现零次或者两次，并使得y-x的绝对值最小

大概思路：去找开方x附近的值，这个值满足所有质因数最多只出现一次，并使得这个值的平方离x尽量的近

一开始的思路想把40000以内的素数打表出来，然后去找这个值，检查值是否满足所有质因数最多只出现一次的check函数这么写：

int check_y(int y){
    if(prime[i]) return 1;
    for(int i=2;i<=sqrt(y);i++){
        if(prime[i]&&!y%i){
            y/=i;
        }
    }
    if(y==0) return 1;
    return 0;
}

但是后面发现其实可以不用找素数，可以改成这么写：

int check_y(int y){
    if(y==1) return 0;
    for(int i=2;i<=sqrt(y);i++){
        if(y%i==0){
            y/=i;
            if(y%i==0) return 0;
        }
    }
    return 1;
}

下面是完整代码：

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#define ll long long
using namespace std;
int check_y(int y){
    if(y==1) return 0;
    for(int i=2;i<=sqrt(y);i++){
        if(y%i==0){
            y/=i;
            if(y%i==0) return 0;
        }
    }
    return 1;
}
int main(){
    int T,pow_y;
    ll x,y,ans,r_pow_x,l_pow_x;;
//    freopen("in.in","r",stdin);
    cin>>T;
    while(T--){
        cin>>x;
        l_pow_x=(ll)sqrt(1.0*x);
        r_pow_x=l_pow_x+1;
        while(true){
            if(l_pow_x&&check_y(l_pow_x)&&check_y(r_pow_x)){
                ans=min(x-l_pow_x*l_pow_x,r_pow_x*r_pow_x-x);
                break;
            }
            if(check_y(r_pow_x)){
                ans=r_pow_x*r_pow_x-x;
                break;
            }
            if(l_pow_x&&check_y(l_pow_x)){
                ans=x-l_pow_x*l_pow_x;
                break;
            }
            if(l_pow_x>0) l_pow_x--;
            r_pow_x++;
        }
        cout<<ans<<endl;
    }
}

码的过程中y平方脑抽用了pow函数可能出现精度问题一直WA，后面改成直接相乘就AC了