BUPT2017 wintertraining(16) #4 C
HDU - 5778
题意
给定x,找出使|y-x|最小,且每个质因子都出现两次的y(\(y\le 2\))50组测试数据,\(1\le x \le 10^{18}\)
题解
因为每个质因子出现两次,所以y一定可以开根号。于是我们枚举sqrt(x)附近的sqrt(y),质因子都只出现一次就是可行的。
比赛的时候我是打好质数表,然后枚举质因子。实际上直接枚举还更快。
代码
#include <cstdio>
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
int n;
ll a,ans;
bool ck(ll x){
if(x<2)return 0;
for(int i=2;i*i<=x;i++)
if(x%(i*i)==0)return 0;
ans=min(ans,abs(x*x-a));
return 1;
}
int main() {
scanf("%d",&n);
while(n--){
ans=1LL<<60;
scanf("%lld",&a);
ll b=sqrt(a),c=b;
for(b++;ck(b)+ck(c)==0;b++,c--);
printf("%lld\n",ans);
}
return 0;
}