把n表示成n=a1^b1*a2^b2*...*ak^bk

然后呢，n^2=a^2+b^2的整数解个数就是对所有ai mod 4=1的bi乘以2+1，然后累乘。

就是说，比如n=2^3*5^4*7^2*13^7

那么被4除余1的因子有5^4和13^7，那么答案就是(4*2+1)*(7*2+1)=135

最后再乘以4！！！所以就是135*4=540

楼下的，这个公式怎么证明呀？？我感觉当n=5时好像就不成立吧？

这里答案就是(1*2+1)*4=12,为什么是十二呀？？这什么意思？？

大牛怎么都说自己是沙茶？

太虚伪了

这题也太**了吧，完全是数学题，貌似很难推导出那个公式……

我们是搞OI的，出这么难的数学题干嘛……

本题MS在2009年上半年的几期里有……

同意楼下的。。。

我是沙茶,orz curimit，orz cgy4ever

方程 x^2+y^2=n的解数

为 4sigma(h(d)| d|n)

其中h(d)= 0 (当2|d)

(-1)^((d-1)/2) (当2不整除d)

参考《初等数论》P284

如果正确方法真的是在这上面简化的话。。。我对出题人无语

搞NOI的人也没几个人知道吧。。。

p和k是质数吗？

这是人做的题啊?

题目说这个是素数那个是素数好像全世界的数都是素数了.

Fermat小定理要求的是模的数是素数,而题目里模的数在迭代的过程中变小,就不一定是素数了.

好不容易昨天比赛里有这么好写的一道题,我就为了懒得写几行求循环节长度的,用错了Fermat小定理..

我是大沙茶,没什么好说的.

第四..很不错了

此题我蒙的

汗……顺序不对……

看来此题是给冲击C.M.O或I.M.O金牌的人做的

PS:我是沙茶,orz curimit

最后一题，很难的，大家认真

var n,i,a,s:longint;

　　 b,c:Array [1..1000] of longint;

begin

readln(n);

for i:=1 to n do

　　begin

　　 read(a);

　　 b[a]:=1;

　　end;

for i:=1 to 1000 do

　　if b[i]=1 then begin inc(s);c:=i; end;

writeln(s);

for i:=1 to s do

　　write(c[i],' ');

writeln;

end.