HDU-5778 abs

原题链接

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1260Accceptedted Submission(s): 439

Problem Description

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

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

511124290871699579095

Sample Output

23656724470

设p1 = sqrt(x), p2 = p1 +1, P1向小方向枚举，P2向大方向枚举，找到一个p使P的每个质因子只有一个，abs(p*p-x)达到最小.

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <vector>#include <map>#include <cmath>#define maxn 100005#define INF 1000000000using namespace std;typedef long long ll;int num[maxn], cnt;ll v[maxn];void prime(){for(ll i = 2; i < maxn; i++){if(num[i] == 0){v[cnt++] = i;}for(ll j = i * i; j < maxn; j += i) num[j] = 1;}}bool judge(ll p){if(p < 2)  return false;for(int i = 0; i < cnt&& v[i] * v[i] <= p; i++){ll d = v[i] * v[i];if(p % d == 0) return false;}return true;}void solve(ll x){ll p1 = sqrt(x);ll p2 = p1 + 1;while(1){if(p1 >= 2 && x - p1 * p1 < p2 * p2 - x){if(judge(p1)){printf(%I64d\n", x - p1 * p1);    return ;}    p1--;}else{if(judge(p2)){printf(%I64d\n", p2 * p2 - x);        return ;}p2++;}}}int main(){//freopen("in.txt", "r", stdin);int t;prime();scanf("%d", &t);while(t--){ll x;scanf(%I64d”， &x);solve(x);} return 0;}