分析

求有多少个点对(x,y)满足x2+y2 = r2

显然，答案是对称的，四个象限的数目是一样的。

而且r是一个整数，所以四个坐标轴都有整点。

设ans是第一象限内的点的数目，则结果就是4*ans+4。

现在我们假设(x>0,y>0)，则y=sqrt((r-x)(r+x))

设d = gcd((r+x),(r-x))

那么显然(r+x)/d与(r-x)/d互质。

设A = (r-x)/d,B = (r+x)/d

则r-x = Ad, r+x = Bd

将其带入等式，则y2 = d2AB

即(y/d)2 = AB

因为x!=0，所以A!=B。

所以A和B都分别是平方数，即A = a2, B = b2。

于是a2 + b2 = (2r)/d 且gcd(a,b)==1

因为A = r-x,B = r+x，所以a<b。

所以a2<r/d

然后我们枚举a和d，求出b，判断是否满足条件即可。

注意，枚举d的时候，有两边，即(2r)/d和d。

#include <bits/stdc++.h>

#define sc(n) scanf("%d",&n)

#define pt(n) printf("%d\n",n)

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define vi vector<int>

#define vl vector<long long>

#define pb push_back

using namespace std;

typedef long long ll;

ll r,ans = 0;

void work(ll k)

{

for(ll a=1;a*a<k/2;a++)

{

ll now = k-a*a;

ll b = sqrt(now);

if(b*b!=now) continue;

if(__gcd(a,b)==1) ans++;

}

}

int main()

{

scanf("%lld",&r);

for(ll d=1;d*d<=2*r;d++)

{

if(2*r%d==0)

{

work(2*r/d);

if(d*d!=2*r) work(d);

}

}

printf("%lld\n",4*ans+4);

return 0;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

---------------------