abs

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 966 Accepted Submission(s): 346

Problem Description

Given a number x, ask positive integer

y≥2, that satisfy the following conditions:
1. The absolute value of y - x is minimal
2. To prime factors decomposition of Y, every element factor appears two times exactly.

Input

The first line of input is an integer T (

1≤T≤50)
For each test case，the single line contains, an integer x (

1≤x≤1018)

Output

For each testcase print the absolute value of y - x

Sample Input

   5 1112 4290 8716 9957 9095  

Sample Output

   23 65 67 244 70  

Source

BestCoder Round #85

思路：

此题的意思是，给定任意x，求使|y-x|最小的y,并且y要满足对它进行质因数分解后每个质因数的指数都是2。

特么的这个题从第一天晚上9点多一直到第二天下午三点才A掉，换了好几种做法，最后A掉的感觉真的是太爽了。

一开始的思路就是想用质因数分解的模板，从x向两边遍历，将各个质因数的指数都储存起来，然后判断，但是用这个方式的结果就是，T掉T掉再T掉，根本运行不起来，看起来很简单的东西常规方法竟然不行。

后来又想用打素数表的方式，看是不是能够快一点，毕竟这样的方法会比第一种方法快很多，不用对每个每个质数多次遍历。但是！做了好久好久啊，突然发现一个问题！这个素数表要打到多少？他喵的题目里说n的数量姐最大是10的18次方，也就是说，可能存在一个10的9次方数量级的质数，它的平方是10的18次方数量级，且满足题意，那这样不就把素数表打到10的9次方了？？？咋不上天呢...但是我还是“脚踏实地”得打了一遍T-T到10的6次的时候程序就跑不动了...

那就再换啊！后来我就想，因为我之前是自己写了一个分解质因数且储存指数的函数，如果把这个函数直接放到函数里呢？应该会少一些东西...说不定就成功了呢hhhhh(内心一直幻想着A掉的那个画面(*-*-*)

那就写呗...写着写着就觉着不对劲，好像越写越麻烦啊...而且如果质数分别是322222222，分明第一个指数就不是2了，难道以后的还需要遍历？

所以就产生了下面的改进版4.0，遍历指数的时候，如果有指数不等于2，就continue。哈哈哈看起来好像快成功了的样子！满怀信心得再提交一次....特么的还是超时！！！

奔溃啊....已经是晚上两点了...就关机了，准备洗洗睡了...然而洗完澡之后又出来打开了电脑（这个没志气的货...）这时候连样例都过不了了...又重新找了一遍bug在哪，可是找不到啊啊啊啊啊啊。内心一万个崩溃，真睡了...

崭新的一天！今天一定要A掉它！

再次打了一遍，这次的改进措施是，我之前是用了两个for循环来分别找y1和y2，这样如果有相同的数要遍历两次，所以这次在for循环里的改变了一下，用flag1==true时表示y1还能再继续找，flag2==true时表示y2还能再继续找，如果有一个找到了它的flag就变成false，这样当flag1!=false||flag2!=false的时候就可以遍历到。但是...还是T...

我开始怀疑人生了- - 试了一下把各个变量输出，我发现如果找y1和y2联系起来的话好像会产生连带的副作用，所以还是把它们俩拆开了找。这次增加了一个细节，就是当x<=4的时候，它往下找是找不到的，所以当x<4时的结果是4-x,x==4时的结果是5，x>4时可以用上面写的办法来做。但是还是T

啊啊啊啊啊要杀人啦

仔细想了一下，大体的想法应该对，思路也对，应该就是对一些数据的处理细节有问题。在对1-100内的数都测试过后它们都可以过，但是如果数很大了的话，100000000000级别的程序就没有反应了。开方！！！一下子把18次方数量级转化为9次方数量级做了~~试想一下，如果y满足它的质因数指数都是2，那么它开根号就是一个整数。但是还是会包含2^4开方后也是一个整数的情况，但是它2的指数在开方后是2，不是1。所以可以对开方后的数进行质因数，如果这个数可以被质因数分解且每个质因数的指数都是1，那么这个数就是符合的。哈哈哈哈哈哈哈哈哈哈哈哈真的好机智啊

这次提交了之后虽然是WA，但是不是T了！！又向成功进了一步！

又分析为什么会WA，在输出了几对y1和y2后，我发现它们在向上找的时候y1都是正确的，但是在向下找的过程中y2却不是它本该出现的值。我的y2是从（int）sqrt（x）开始向下找的，WA了。试想一下，如，如果开完根号是66.6，那么它向下找的话应该从66开始，也就是（int）sqrt（x）；如果向上找的话就是从67开始找，也就是（int）sqrt（x）+1。这题提交就AC掉了~~~~

最终版本是加强版8.0，总共提交了17次...最后过的时候真的是开心...

贴上我的终极强化版8.0代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 100000

long long a[maxn];
long long b[maxn];

bool factor(int n)
{
    for(int i=2;i<=sqrt(n);i++){
		if(n%i==0){
			while(n%i==0){
				n=n/i;
				if(n%i==0) return false;
			}
		}
	}
	return true;
}

int main()
{
    int num;
    scanf("%d",&num);
    while(num--)
    {
        long long xx;
        long long x;
        long long y;
        scanf("%lld",&xx);
        x=(int)sqrt(xx);
        y=x+1;
        long long cnt=0;
        long long y1=0,y2=0;
        
        bool flag=false;
        
        if(xx<4)
        {
        	cout<<4-xx<<endl;
        	continue;
        }
        if(xx==4)
        {
        	cout<<5<<endl;
        	continue; 	
        }
        
        
        for(long long j=1;;j++)
        {
	        if(factor(x+j)==true)
			{
					y1=(x+j)*(x+j);
					break; 
		 	}      
        
        }
        
         cnt=0;
         for(long long j=1;;j++)
        {
        	if(fabs(y1-xx)<=fabs((y-j)*(y-j)-xx))
        	{
        		break;
        	}
            else if(factor(y-j)==true)
			{
					y2=(y-j)*(y-j);
					break;
		 	} 
	    } 
       // cout<<y1<<" "<<y2<<endl;
        long long s=min(fabs(y1-xx),fabs(y2-xx));
        printf("%lld\n",s);
    }
}

希望我能在ACM道路上越走越远...

HDOJ 5778 abs（质因数分解）

abs