HDU 5778 abs 数论

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5778

　　题目描述：给出一个数X，让你求出一个数num，使得abs(x-num)最小，且num素数分解每个数都是2次方

　　解题思路，每个数都是2次方，开根号每个数就都是一次方，就是一个都是单个素数相乘的数，我们将x开根号，然后两头分别判断是否符合条件就可以了，我们最差情况就是10^9，由于素数的分布非常的密集，所以基本上很快就会产生一个符合条件的数

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define sca(x) scanf("%d",&x)
#define de printf("=======
")
typedef long long ll;
using namespace std;

ll t1, t2;
ll func( ll n ) {
    
    for( ll i = 2; i*i <= n; i++ ) {
        if( n % i == 0 ) {
            int cnt = 0;
            while( n % i == 0 ) {
                cnt++;
                n /= i;
                if( cnt > 1 ) return 0;
            }
        }
    }
    return 1;
}

int a[100];

int main() {
    int t;
    sca(t);
    while( t-- ) {
        ll x;
        scanf( "%lld", &x );
        t1 = (ll)sqrt(double(x));
        t2 = (ll)sqrt(double(x))+1;
        ll ans1 = -1;
        ll ans2 = -1;
        while( 1 ) {
            if( t1 >= 2 ) {
                if( func( t1 ) ) {
                    ans1 = t1;
                }
            }
            if( t2 <= (ll)1e9 ) {
                if( func( t2 ) ) {
                    ans2 = t2;
                }
            }
            if( ans1 != -1 || ans2 != -1 ) break;
            t1--, t2++;
            
        }
//        cout << t1 << " " << t2 << endl;
        ll res = -1;
        if( ans1 == -1 ) res = ans2;
        else if( ans2 == -1 ) res = ans1;
        else {
            ll c1 = abs(x-t1*t1);
            ll c2 = abs(x-t2*t2);
            if( c1 > c2 ) res = t2;
            else res = t1;
        }
        printf( "%lld
", abs(x-res*res) );
    }
    return 0;
}

View Code

　　思考：自己之前犹豫了一下复杂度，没敢算，就从将x素数分解开始想，后来想回过神儿来，还WA了一发，因为忘了加绝对值了，是真的马虎啊