BestCoder Round #85 1003 abs

问题描述

给定一个数x，求正整数$y\ge 2$，使得满足以下条件： 1.y-x的绝对值最小 2.y的质因数分解式中每个质因数均恰好出现2次。 输入描述 第一行输入一个整数T（$1\le T\le 50$) 每组数据有一行，一个整数x（1≤x≤10181\leq x\leq {10}^{18}1≤x≤10​18​​) 输出描述 对于每组数据，输出一行y-x的最小绝对值 输入样例 5 1112 4290 8716 9957 9095 输出样例 23 65 67 244 70

思路：

因为每个质因子恰好出现两次，所以可以开平方到10的9次，10的9次方内的数相邻两质数距离不超过三百，因为质数是肯定满足条件的所以答案就在距离x最近的两相邻质数区间内。这样只需前后暴力排除就行，注意往前找的时候有停止范围（1），排除的方法是素数打表，挨个排...

代码：

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #define MAX_N 100000 + 1 using namespace std; typedef __int64 LL; int h; LL prime[MAX_N]; ///第i个素数 bool is_prime[MAX_N + 1];/// is_prime[i]为true表示i为素数 // 返回n以内素数的个数 int sieve(int n) { int p = 0; for(int i = 2; i <= n; i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for(int i = 2; i <= n; i++) { if(is_prime[i]) { prime[p++] = i; for(int j = 2*i; j <= n; j += i) is_prime[j] = false; } } return p; } bool operat(int n) { for(int i = 0; i < h && 1LL*prime[i]*prime[i]<=n; i++) if(n%(1LL*prime[i]*prime[i])==0) //说明该数的因子中至少有两个prime[i]; return false; return true; } int main() { int n; cin>>n; h = sieve(40000); while(n--) { long long x,x1,y1; scanf("%I64d",&x); long long xx = 1LL*sqrt(x*1.0); for(x1 = xx; x1 >= 2; x1--) if(operat(x1)) break; for(y1 = xx+1;;y1++) if(operat(y1)) break; if(x1 >= 2) printf("%I64d\n",min(x-x1*x1,y1*y1-x)); else printf("%I64d\n",y1*y1-x); } return 0; }