原题链接
题目描述：求一个给定的圆(x^2+y^2=n^2)，在圆周上有多少个点的坐标是整数。
输入格式：只有一个正整数n,n<=2e9
输出格式：整点个数
输入样例： 4
输出样例： 4
解析：推到一半就不会了，果然我还是太菜~ 题目要求 \(x^2 + y^2 = n^2\) 那么 \(n^2 - x^2 = y^2\) \((n + x)(n - x)=y^2\) 设d = gcd(n + x, n - x) 那么 n + x = \(d \times v\), n - x = \(d \times u\)，\(u < v\)，gcd(u, v) == 1 因为两数相乘是个完全平方，所以u和v都是完全平方 设 u = \(a^2\) , v = \(b^2\)，\(a < b\)，gcd(a, b) == 1 所以 n + x = \(d \times b^2\)，n - x = \(d \times a^2\) 两式相加，n = \(d \times (a^2+b^2)\div2\) \(2 \times n = d \times (a^2 + b^2)\) 所以可以枚举 2n 的每个因数，再枚举a，最后判断b是否合法即可 注意要判断gcd(a, b) = 1，并且a < b 这样就算出了第一象限的答案，最后将答案乘4即可
代码如下：
#include<cstdio> #include<cmath> #define ll long long using namespace std; const int maxn = 1e5 + 5; int ve[maxn], tot; ll n, ans; int gcd(int x, int y) { if (!y) return x; else return gcd(y, x % y); } int main() { scanf("%lld", &n); n <<= 1; for (int i = 1; i <= sqrt(n); ++ i) { //找出所有的因数 if (n % i == 0) { int a = n / i, b = i; if (a != b) ve[++ tot] = a, ve[++ tot] = b; else ve[++ tot] = a; } } for (int i = 1; i <= tot; ++ i) { ll tmp = n / ve[i]; for (int j = 1; j <= sqrt(tmp); ++ j) { ll a = j, b = sqrt(tmp - a * a); if (a > b) break; //a不能大于b if ((gcd(a, b) == 1) && (b * b == tmp - a * a)) ans ++; //合法就统计答案 } } printf("%lld", ans << 2); //最后将答案乘4 return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10072536.html
相关资源：JAVA上百实例源码以及开源项目