bzoj 1041 数学推理

原题传送门http://www.lydsy.com/JudgeOnline/problem.php?id=1041

我们只需要求第一象限内（不包括坐标轴）的点数然后ans=ans*4+4就好了

首先我们知道圆上点的方程关系

x*x+y*y=r*r

那么我们变下型

Y*Y=R*R-X*X

Y*Y=(R-X)*(R+X) ①

我们令d=gcd(r-x,r+x)

设A=（r-x)/d;

B=(r+x)/d;

因为我们要求x为整数，那么需要A,B为整数

将A,B带回①可得

A*B*d*d=y*y

因为我们要求y为整数，那么需要A*B*d*d为完全平方数

因为点在第一象限内，所以A<>B,所以A,B应为完全平方数

那么当A,B为完全平方数时，x,y为整数

那么我们可以设A=a*a; B=b*b;

则有a*a=(r-x)/d; b*b=(r+x)/d;

那么两式相加，得到a*a+b*b=2*r/d；

那么只要a,b为整数，就可以得到一组整点

那么我们可以知道d|2*r

所以我们可以枚举2*r的因数，对于每个因数（每个因数对应一对儿因数，分别是d和2*r/d）

假设因数是d的时候，因为a<b所以2*a*a<2*r/d，所以a*a<r/d 那么我们可以枚举a<sqrt(r/d)，

对于每个a我们可以算出b,相对应的A,B应满足gcd(A,B)=1且A<>B如果满足，就累加答案

 1 /**************************************************************
 2     Problem: 1041
 3     User: BLADEVIL
 4     Language: Pascal
 5     Result: Accepted
 6     Time:136 ms
 7     Memory:224 kb
 8 ****************************************************************/
 9  
10 //By BLADEVIL
11 var
12     r                           :int64;
13     ans                         :int64;
14      
15 function gcd(a,b:int64):int64;
16 begin
17     if b>a then exit(gcd(b,a)) else
18     if b=0 then gcd:=a else gcd:=gcd(b,a mod b);
19 end;
20      
21 function check(y:int64;x:extended):boolean;
22 var
23     x1                          :int64;
24 begin
25     if x=trunc(x) then
26     begin
27         x1:=trunc(x);
28         if (gcd(x1*x1,y*y)=1) and (x1*x1<>y*y) then
29         begin
30             exit(true);
31         end;
32     end;
33     exit(false);
34 end;
35      
36 procedure main;
37 var
38     d, a                        :longint;
39     b                           :extended;
40 begin
41     read(r);
42     for d:=1 to trunc(sqrt(2*r)) do
43     begin
44         if (2*r) mod d=0 then
45         begin
46             for a:=1 to trunc(sqrt(r/d)) do
47             begin
48                 b:=sqrt(((2*r)/d)-a*a);
49                 if check(a,b) then ans:=ans+1;
50             end;
51             if d<>((2*r) div d) then
52             for a:=1 to trunc(sqrt(d/2)) do
53             begin
54                 b:=sqrt(d-a*a);
55                 if check(a,b) then ans:=ans+1;
56             end;
57         end;
58     end;   
59     writeln(ans*4+4);
60 end;
61  
62 begin
63     main;
64  
65 end.