回 帖 发 新 帖 刷新版面

主题:看似容易实际很难的题目

Description
Given an odd prime p.
You are to tell whether p can be written into form a^2+b^2 (0 and if p can be done, you are to determine a pair of a,b.


Input
There will be up to 2*10^5 test cases.
An odd prime p (3<=p<2*10^9) in each line.
End with EOF.


Output
For each number p,
if p can be written into form a^2+b^2 (0 output one line that contains "Legal a b",
and if not just output one line that contains "Illegal".
For a certain p that can be written into the form described above, any pair of a,b (0

Sample Input

3
5
7
11
13
17
19
23
29


Sample Output

Illegal
Legal 1 2
Illegal
Illegal
Legal 2 3
Legal 1 4
Illegal
Illegal
Legal 2 5


我想看看有没有大侠能做出来这道题。

回复列表 (共4个回复)

沙发

没有人

板凳

判断数A:
K从1到SQRT(A/2);
如果SQRT(A-K*K)是整数则输出之,标记找到XX后并结束循环;
如果不是XX则输出Illegal。

3 楼

给一个不好的算法(既然说了给出的是一个质数,那么就可以充分利用这一个条件):
 1. 先判断这个数是不是素数,如果是输入得到这个数,那么它不一定是素数。
 2. 判断这个素数是不是2,或者是不是 4*k+3 这种形式,这种形式的素数是绝对不能写成2个平方数之和的。
 3.(我的猜测:4*k+1这种形式的素数应该都可以写成2个平方数之和的。)4*k+1这种形式的素数如果能的话必然要写成一奇一偶两个平方数之和。不妨设这个质数 4*k+1 = (2*a)^2+(2*b+1)^2;这样就有 k = a^2 + b*(b+1),很显然k和a的奇偶性是一样的。这样如果让i变化的话,可以让步长为4,即可以是 i += 4 或者 i -= 4 。

4 楼

你好.我是全职网赚工作者.
如果你有时间有电脑.
想在网络上创业.请联系我..
项目绝对真实.详情QQ空间资料
加盟请联系 QQ908889846

我来回复

您尚未登录,请登录后再回复。点此登录或注册