本文共 1565 字，大约阅读时间需要 5 分钟。
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5778
题目描述： 给出一个数X， 让你求出一个数num， 使得abs(x-num)最小， 且num素数分解每个数都是2次方
解题思路， 每个数都是2次方， 开根号每个数就都是一次方， 就是一个都是单个素数相乘的数， 我们将x开根号， 然后两头分别判断是否符合条件就可以了， 我们最差情况就是10^9， 由于素数的分布非常的密集， 所以基本上很快就会产生一个符合条件的数
代码：
#include #include #include #include #include #include #include #include #include #include #include #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("=======\n")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\n", abs(x-res*res) ); } return 0;}
思考： 自己之前犹豫了一下复杂度， 没敢算， 就从将x素数分解开始想， 后来想回过神儿来 ，还WA了一发， 因为忘了加绝对值了， 是真的马虎啊
转载于:https://www.cnblogs.com/FriskyPuppy/p/7446139.html
