【HDU5778】abs（數學）

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;
}
           

┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆　┆可┆有┆謙┆戮┆那┆　┆大┆始┆　┆然┆

┆薄┆一┆臨┆你┆的┆還┆沒┆　┆來┆　┆是┆來┆遜┆沒┆些┆　┆雁┆終┆　┆而┆

┆　┆暖┆　┆如┆地┆站┆有┆　┆也┆　┆我┆　┆的┆有┆精┆　┆也┆沒┆　┆你┆

┆　┆這┆　┆試┆方┆在┆逃┆　┆會┆　┆在┆　┆清┆來┆準┆　┆沒┆有┆　┆沒┆

┆　┆生┆　┆探┆　┆最┆避┆　┆在┆　┆這┆　┆晨┆　┆的┆　┆有┆來┆　┆有┆

┆　┆之┆　┆般┆　┆不┆　┆　┆這┆　┆裡┆　┆沒┆　┆殺┆　┆來┆　┆　┆來┆