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
4290
8716
9957
9095
Sample Output
23
65
67
244
70
65
67
244
70
描述：
给你一个long long范围的数x，然后让你找到一个数y，数y的质因数分解中，每个数刚好出现两次，输出的是abs（x-y）最小。
题解：
比赛的时候没想出来，后来看题解发现竟然这么水= =。
官方题解：由于y质因数分解式中每个质因数均出现2次，那么y是一个完全平方数，设y=z*z，题目可转换成求z，使得每个质因数出现1次. 我们可以暴力枚举z，检查z是否符合要求，显然当z是质数是符合
要求，由素数定理可以得，z的枚举量在logn级别 复杂度 O（\sqrt[4]{n}log\sqrt[2]{n}4√nlog2√n）；
就只需要在x周围枚举就好了，枚举的范围题解说很小。。。然后z判断是不是满足条件的也很简单。
代码：
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#define inf 9223372036854775807
#define INF 9e7+5
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e5 + ;
const int mod = 1e9 + ;
const db eps = 1e-; // 判断这个数满不满足条件。
bool ok(ll x) {
for (ll i = ; i*i <= x; i++) {
int num = ;
while (x % i == ) { /*这里的i满足while的条件肯定是素数，为什么呢，就和素数筛选法的原理差不多。*/
num++;
x /= i;
if (num > ) return false;// 如果大约两次就不满足条件
}
}
return true;
} ll abss(ll x) {
return x >= ? x : -x;
} void solve() {
ll n, ans; cin >> n;
ll z = sqrt(n+0.5D);
//cout << z << endl;
for (ll i = ; ; i++) {
ll tmp = z + i;
if (tmp * tmp >= n && ok(tmp)) { /*因为不比比n小，所以要满足 >= n这个条件，测试样例的时候发现8开方是2，然后2是满足条件的，此时找到的答案就不对。*/
ans = abss(tmp*tmp - n);
//cout << tmp << endl;
break;
}
}
for (ll i = ; ;i++) {
ll tmp = z - i;
if (ok(tmp)) {
ans = min(ans, abs(tmp*tmp - n));
break;
}
}
if (n < ) ans = - n; /*小于4的开方都是1，然后用ok函数判断的1是满足条件的，但是1不是素数，所以要特判。*/
cout << ans << endl;
} int main()
{
//cin.sync_with_stdio(false);
//freopen("isharp.in", "r", stdin);
//freopen("hh.txt", "w", stdout);
int t; cin >> t; while (t--)
solve();
return ;
}