HDU_5778

思路

由于y质因数分解式中每个质因数均出现2次，那么y是一个完全平方数，设y=z*z，题目可转换成求z，使得每个质因数出现1次. 我们可以暴力枚举z，检查z是否符合要求，显然当z是质数是符合要求，由素数定理可以得，z的枚举量在logn级别

感受

这道题一开始做的时候我知道我是处理不了10^18的数据的，只是死马当活马医，竟然好让我给AC了，当然最后还是送了别人50分的hack。后来是看了学长的代码，思考了很久，发现自己有三个地方写的不行，数感也不敏锐。在聪明的卓君的帮助下终于是理解，为什么10^5的prime数组就能解决10^18数据。

数学证明

1
2
3
4
5
6
7
8
9
bool judg(ll x){
	for(int i=1;i<=cnt && ned[i] * ned[i] <=x;i++){
		if(x%ned[i]==0){
			x/=ned[i];
			if(x%ned[i]==0)return 0;
		}
	}
	return 1;
}

设100007是大于10^5最小的素数。则100007100007是不符合条件但是上面代码是return 1的。
可是别忘了，我们之前开根号过，所以我们还原数据，平方一下得100007100007100007100007 > 10^20
超出了数据范围，所以在数据范围里是不可能有特例的。

好筛法

1
2
3
4
5
6
7
8
9
10
11
void isprime(){
	cnt=0;
	for(int i=0;i<maxn;i++) prime[i]=1;
	for(ll i=2;i<maxn;i++){
		if(prime[i])ned[++cnt]=i;
		for(ll j=1; j<=cnt && i*ned[j] <= maxn ;j++){
				prime[i * ned[j]] = 0;
				if(i % ned[j] == 0)break;
		}
	}
}

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-10
#define ll long long 
#define maxn 100005
bool prime[maxn];
ll ned[maxn],cnt;
void isprime(){
	cnt=0;
	for(int i=0;i<maxn;i++) prime[i]=1;
	for(ll i=2;i<maxn;i++){
		if(prime[i])ned[++cnt]=i;
		for(ll j=1; j<=cnt && i*ned[j] <= maxn ;j++){
				prime[i * ned[j]] = 0;
				if(i % ned[j] == 0)break;
		}
	}
}
bool judg(ll x){
	for(int i=1;i<=cnt && ned[i] * ned[i] <=x;i++){
		if(x%ned[i]==0){
			x/=ned[i];
			if(x%ned[i]==0)return 0;
		}
	}
	return 1;
}
int main()
{
	isprime();
	int n;
	cin>>n;
	while(n--){
		ll x,ans1,ans2;
		scanf("%I64d",&x);
		ll tmp=sqrt(x*1.0);
		bool left=0,right=0;
		for(ll i=1; ;i++)
		{
			if(left==0 && judg(tmp-i+1)){
				if(2 > (tmp-i+1)) ans1=abs(4-x);//特别注意呦！第一个符合条件的是4
				else ans1=abs((tmp-i+1)*(tmp-i+1)-x);
				left = 1;
			}
			if(right==0 && judg(tmp+i) ){
				if(2 > (tmp+i)) ans2=abs(4 - x);
				else ans2=abs((tmp+i)*(tmp+i)-x);
				right = 1;
			}
			if(left && right) break;
		}
		printf("%I64d\n",min(ans1,ans2));
	}
   return 0;
}