hdu-5778 abs(暴力枚举)

题目链接:

abs

Time Limit: 2000/1000 MS (Java/Others)   

 Memory Limit: 131072/131072 K (Java/Others)

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

5

1112

4290

8716

9957

9095

Sample Output

23

65

67

244

70

题意：

给一个x,然后让你找一个y,分解质因子后y的质因子次幂均为2,使abs(y-x)最小;

思路：

枚举x周围的那些数,看是否符合条件然后更新答案就好了;

AC代码：

/************************************************ 
┆  ┏┓　　　┏┓ ┆    
┆┏┛┻━━━┛┻┓ ┆ 
┆┃　　　　　　　┃ ┆ 
┆┃　　　━　　　┃ ┆ 
┆┃　┳┛　┗┳　┃ ┆ 
┆┃　　　　　　　┃ ┆  
┆┃　　　┻　　　┃ ┆ 
┆┗━┓　  　┏━┛ ┆ 
┆　　┃　  　┃　　┆　　　　　　 
┆　　┃　  　┗━━━┓ ┆ 
┆　　┃　 AC代马 　　┣┓┆ 
┆　　┃　        　　┏┛┆ 
┆　　┗┓┓┏━┳┓┏┛ ┆ 
┆　　　┃┫┫　┃┫┫ ┆ 
┆　　　┗┻┛　┗┻┛ ┆       
************************************************ */  #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>using namespace std;#define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss));typedef  long long LL;template<class T> void read(T&num) {char CH; bool F=false;for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {if(!p) { puts("0"); return; }while(p) stk[++ tp] = p%10, p/=10;while(tp) putchar(stk[tp--] + '0');putchar('\n');
}const LL mod=1e9+7;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=1e5+10;
const int maxn=1e5+4;
const double eps=1e-8;int cnt,vis[N],prime[N];
inline void Init()
{cnt=0;For(i,2,maxn){if(!vis[i]){for(int j=2*i;j<maxn;j+=i)vis[j]=1;prime[++cnt]=i;}}
}inline int check(LL  x)
{for(int i=1;i<=cnt;i++){if(x<prime[i])break;if(x%prime[i]==0){x=x/prime[i];if(x%prime[i]==0)return 0;}}return 1;
}int main()
{       int t;read(t);Init();while(t--){LL n;read(n);LL temp=sqrt(n+0.5),ans=inf;int flag=0;for(LL i=0; ;i++){if(check(temp+i)&&(temp+i)*(temp+i)>=2){ans=min(ans,abs((temp+i)*(temp+i)-n));flag=1;}if(check(temp-i)&&temp>i&&(temp-i)*(temp-i)>=2)ans=min(ans,abs((temp-i)*(temp-i)-n)),flag=1;if(flag&&i>=6)break;}cout<<ans<<"\n";}return 0;
}