绝对值(HG 2018.5.13 T1)

2018-05-13 18:54:54


【问题描述】

给定一个数 x,求正整数 y≥2,使得满足以下条件: 1.y-x 的绝对值最小; 2.y 的质因数分解式中每个质因数均恰好出现 2 次。

【输入数据】

第一行输入一个整数 T(1≤T≤50) 每组数据有一行,一个整数 x(1≤x≤10^18) 【输出数据】 对于每组数据,输出一行 y-x 的最小绝对值。

【输入样例 1】

5

1112

4290

8716

9957

9095

【输出样例 1】

23

65

67

244

70

【数据范围】

对于 20% 的数据, T = 1, x ⩽ 10^4 对于 50% 的数据, T ⩽ 10, x ⩽ 10^12 对于 70% 的数据, T ⩽ 30, x ⩽ 10^15 对于 100% 的数据, T ⩽ 50, x ⩽ 10^18

【题目来源】

HDU5778

因为每个质因数恰好出现 2 次,所以 y 必定是一个完全平方数 假设 y=z*z 那么 z 必定是一个由不同质数构成,且每种质数仅有一个的 10^9 以内的整数 对于一个 10^9 范围内的数,若它在sqrt(10^9)之内没有找到因子的话,那这个数必定是一个质数 显然,z 为质数时也是满足的。 那么我们就从 sqrt(x)开始,分别向下,向上枚举,直到找到符合题意的 z,哪个|y-x|小就取哪个 特判 x<4 的情况,因为题目规定 y>=2

代码如下:

#include<cmath> 
#include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<algorithm> 
using namespace std;
long long read()
{
    long long x=0,flag=0;
    char ch=getchar();
    if(ch=='-') flag=1;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar();
    if(flag) return -x;
    return x;
}
bool can(long long x)//判断x是否满足质因数分解后每个质因数恰好出现一次
{
    for(long long i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            int num=0;
            while(x%i==0)
            {
                x/=i;
                num++;
                if(num>1) return 0;
            }
        }
    }
    return 1;
}
int T;
int main()
{
    freopen("abs.in","r",stdin);
    freopen("abs.out","w",stdout);
    T=read();
    while(T--)
    {
        long long a=read();
        long long b=sqrt(a);
        long long i,j;
        if(a<=4)
        {
            cout<<4-a<<endl;
            continue;
        }
        for(i=b+1;i<=10000000000;i++)//i=b是不行的,因为有可能在i=b的的时候就弹出,而当i=b+1是实际上也可以并且答案更小
            if(can(i)) break;//向上枚举
        for(j=b;j>=2;j--)
            if(can(j)) break;//向下枚举
        printf("%lld\n",min(abs(i*i-a),abs(a-j*j)));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}