logo标签列表

给定整数n，判断是否可能将其表示为两个整数的平方和。

c++c
3

输入要求:

第一行输入一个整数 t <= 10000 ：测试用例的数量。 接下来 T 行，每行输入一个整数，范围为 0 <= n <= 10^8。

输出要求:

对于每个测试用例，如果可以将给定数字表示为两个平方数的和，则输出 Yes，否则输出 No。

1
你需要一个算法还是你已经有一个太慢了？ - flight
5
这里不是你可以将作业要求放下后再来取解决方案的地方。如果你在编码的某个特定方面遇到了问题，可以随时问我。 - GManNickG
4
两件事。1）这是C还是C ++？区别很重要。2）请发布你迄今为止的尝试，然后我们将看看是否可以帮助您理解其中具体的部分。如果您没有任何起点，您将得不到太多帮助！ - corsiKa
1
你忘记了时间和内存限制。这似乎是一个经典的ACM算法问题。 - galymzhan
1个回答
3
提示：一个数字N可以表示为两个平方数的和，当且仅当在N的质因数分解中，形如（4k+3）的每个质数出现次数都是偶数时成立！
1
+1。如果您也能发布证明，那就更好了。 :-) - Nawaz
1
@Nawaz：这个链接可能会有帮助。 - Prasoon Saurav
这是我在网站上的第一个问题...找到了一些代码，但是它们是针对给定整数或整数总和的.. 对于这个问题没有想法，所以正在寻找提示..我不需要完整的算法..@prasoon 谢谢 - Karan Veer Singh
@glowcoder，用C语言编写的代码会对我有所帮助 :) :gman..这不是作业...这是我每天解决的一道小测验问题。 - Karan Veer Singh
是的，这是众所周知的，证明相当庞大。不过这并不是一个编程问题。 - CashCow
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接