CSU-ACM Online Judge

1344: Special Judge

      Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 133     Solved: 69     SpecialJudge

Description

Given a positive integer n, find two non-negative integers a, b such that a2 + b2 = n.

Input

The first line contains the number of test cases T (1 <= T <= 1000).
For each test case, there is only one line with an integer n (1 <= n <= 109) as defined above.

Output

For each test case, output two integers a, b separated by a single space such that a2 + b2 = n. If there are multiple solutions, anyone will be accepted. If there is no solution, output “-1” (without quotation marks) instead.

Sample Input

4
2
3
4
4

Sample Output

1 1
-1
0 2
2 0

Hint

还记得我们在“A Sample Problem”中说到的OJ的判题形式吗?这个题主要让我们来熟悉一下OJ的另一种名为Special Judge的判题形式。所谓的Special Judge是指OJ将使用一个特定的程序来判断我们提交的程序的输出是不是正确的,而不是单纯地看我们提交的程序的输出是否和标准输出一模一样。
一般使用Special Judge都是因为题目的答案不唯一,更具体一点说的话一般是两种情况:
(1)题目最终要求我们输出一个解决方案,而且这个解决方案可能不唯一。比如这个题目就是这样的,只要求我们输出一组a、b满足a^2 + b^2 = n,而对于不同的n,可能有多组a、b满足这一条件,像n=4时,就有a=2、b=0和a=0、b=2这两组解,这时我们输出任意一组解都可以。
(2)题目最终要求我们输出一个浮点数,而且会告诉我们只要我们的答案和标准答案相差不超过某个较小的数就可以,比如0.000001。这种情况我们只要保证我们的中间运算过程尽可能精确就可以了,并且最后输出答案的时候保留的小数位数足够多就行了,比如如果要求我们的答案和标准答案相差不超过0.01,那么一般我们保留3位小数、4位小数等等都是可以的,而且多保留几位小数也没什么坏处。
为了能让大家更清楚的了解Special Judge的原理,这里我把这个题目的执行Special Judge功能的程序的源代码贴出来了。


大家也许发现了,这个执行Special Judge功能的程序并不那么完美,比如我们在输出a和b的时候中间如过用两个空格分隔a和b的话也是可以通过这个题目的,但是这样实际上是不符合题目在Output中约定的输出格式的。我在这里之所以用了这样一个不是很完美的Special Judge,主要原因是写一个十分完美的Special Judge是要花费很大“力气”的,而且有些时候输出的格式并不不是这个题目的核心,更重要的应该是我们输出的a和b应当是符合要求的。不过大家千万不能凡是遇到Special Judge的题目就不管输出格式了,因为并不是所有写Special Judge程序的人都会像我这样偷工减料,我们最好还是要严格按照题目的要求来输出答案。
接下来我们分析一下这个题目应当怎么解决。
最容易想到的办法就是枚举所有可能的a、b,看是否存在一组a、b满足a^2 + b^2 = n。那么所有的可能的a、b有多少呢?最起码的一个限制条件就是a<=n且b<=n,不过我们还能让限制条件更“精确”一些,就是a<=sqrt(n)且b<=sqrt(n),虽然这样枚举量减少了不少,但是我们枚举所有可能的a、b的话还是要枚举sqrt(n)*sqrt(n) = n次,由于n最大可能是10^9,这样的枚举量还是不能承受。
但其实我们是没有必要枚举b的,因为当a确定时b=sqrt(n - a^2),我们可以将b直接求出来,如果b是整数的话,我们就算找到了一组解。这样如果我们枚举完所有可能的a后还没找到一组解的话,就可以说明是无解了。
如果觉得代码写起来会有困难的话,可以参考一下我在下面给出的示例代码,不过最后一定要按自己的思路写一个完整的代码(编写自己的代码时就不要再参考示例代码了,要一气呵成~)并获得“Accept”哟!O(∩_∩)O~
这个程序在计算b时实际上是在计算满足b^2 <= n - a^2的最大的b,之后再判断是否满足a^2 + b^2 = n就可以了。计算b的代码是b=(int)sqrt(n - a^2 + 0.5),之所以+0.5,一个原因是因为这样不会改变计算结果(也就是说这样求出来的仍是满足b^2 <= n - a^2的最大的b),另一个原因是怕出现浮点数误差(也就是说假如真的存在整数b满足a^2 + b^2 = n,通过(int)sqrt(n - a^2)未必能计算出正确的b,因为毕竟sqrt()这个函数是浮点数运算,万一算出的b丢失了一些精度那么向下取整之后就会变成b-1了)。


Source

ACM入门示例(第一季)