1041: [HAOI2008]圆上的整点

Description

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
Input

r
Output

整点个数
Sample Input
4
Sample Output
4
HINT

n<=2000 000 000

不会做，膜拜神犇的题解

 1 var
 2     r:int64;
 3     ans,d:longint;
 4 
 5 function gcd(a,b:int64):int64;
 6 var
 7     t:int64;
 8 begin
 9     while b<>0 do
10       begin
11         t:=a mod b;
12         a:=b;
13         b:=t;
14       end;
15     exit(a);
16 end;
17 
18 procedure slove(r:int64);
19 var
20     i:longint;
21     j:int64;
22 begin
23     for i:=1 to trunc(sqrt(r)) do
24       begin
25         j:=trunc(sqrt(r-i*i));
26         if i>=j then break;
27         if (int64(i)*i+int64(j)*j=r) and (gcd(i,j)=1) then inc(ans);
28       end;
29 end;
30 
31 begin
32     read(r);
33     r:=r<<1;
34     for d:=1 to trunc(sqrt(r)) do
35       begin
36         if r mod d<>0 then continue;
37         slove(r div d);
38         if int64(d)*d=r then break;
39         slove(d);
40       end;
41     write(ans<<2+4);
42 end.

View Code