题目链接:
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.
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)
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;
}