HDU 5778 abs 数学

http://acm.hdu.edu.cn/showproblem.php?pid=5778

这题的意思就是找离x最近的一个数y，且y是一个完全平方数，还是所有质因子都只能出现两次的完全平方数

一开始的思路是直接枚举这个差值，然后去两边找，val - res和val + res找，然后超时了。

其实也很正常，因为两个完全平方数的间隔实在太大了。中间有很多的数字，

那么把思路换一下，

题意是找a^2   <=  x  <=  b^2这样子的东西，那么可以同时开方，a <= sqrt(x) <= b

这样找到的结果是一样的，然后就相当于找一个没有质因子出现过两次的数字了。

先来证明一下为什么筛素数到1e6就够了。我们要判断到1e9之内。

我们现在要找的是，不能出现多个相同质因子相乘出来的数，因为我们开方了嘛。那么，筛到1e6就够了。

对于小的素数，那么肯定可以啦，2 * 2 * ...那些肯定可以筛出来，那么大素数呢？

就是2 * bigprime <= 1e9的那些数。那些也是可以筛出来的，对于大于1e6的素数，我们确实没办法判断，但是如果它在

前面的1e6那里的小素数，都没有出现多个相同质因子相乘的话，那就是可以得了。筛不到的大质因子，就默认可以了。

因为没可能是两个bigPrime相乘的。爆了1e9了。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e6 + ;

int prime[maxn], total;

bool check[maxn];

void initprime() {

    for (int i = ; i <= maxn - ; ++i) {

        if (!check[i]) {

            prime[++total] = i;

        }

        for (int j = ; j <= total; ++j) {

            if (i * prime[j] > maxn - ) break;

            check[i * prime[j]] = ;

            if (i % prime[j] == ) break;

        }

    }

}

bool isok(LL val) {

    if (val < ) return false;

    bool flag = false;

    for (int i = ; i <= total; ++i) {

        if (val < prime[i]) break;

        if (val % prime[i] == ) {

            val /= prime[i];

            if (val % prime[i] == ) return false;

            flag = true;

//            while (val % prime[i] == 0) {

//                val /= prime[i];

//                has++;

//                if (has == 3) return false;

//                flag = true;

//            }

        }

    }

//    if (val != 1) return false;

    return true;

}

void work() { // big prime * big prime  TLE   && 2^6 not ok

    LL val;

//    scanf("%I64d", &val);

    cin >> val;

    LL tpos = val;

    val = (LL)sqrt(val * 1.0);

    LL mid = 2e18;

    if (isok(val)) {

        mid = val * val;

    }

    LL big = 2e18, small = 2e18;

    for (int res = ; ; ++res) {

        if (isok(val + res)) {

            big = (val + res) * (val + res);

            break;

        }

    }

    for (int res = ; ; ++res) {

        if (val - res < ) break;

        if (isok(val - res)) {

            small = (val - res) * (val -res);

            break;

        }

    }

    LL ans = min(abs(tpos - big), abs(tpos - small));

    ans = min(ans, abs(tpos - mid));

//    cout << big << " " << mid << " " << small << endl;

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

//    IOS;

    initprime();

//    cout << isok(33) << endl;

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}