[bzoj 1041] [HAOI2008] 圆上的整点

给定r, 求圆x^2 + y^2 = r^2上整点的数目. (r是正整数, r≤2e9) 之前看 <什么是数学> 学到一个生成勾股数的公式, 然而我对它的理解并不透彻. 头脑中有这样一组公式:

但是它的行为非常奇怪. 当且, 并不能生成所有勾股数. 而且, 这组公式只能生成而不能生成, 或者说所有都是偶数. 的大小关系也是不确定的.

翻了翻书, 原来还有这样的说明: , 则上述公式生成所有互质的毕达哥拉斯三元数. 对于不互质的那些, 还得乘上有理比例因子.

是有理数, 不好办. 就算它是正整数, 枚举的所有因子, 再对每个因子根号复杂度地枚举, 这时间复杂度承受得了吗?

看了题解, 还真承受得了. 有关时间复杂度的讨论见: [bzoj 2705] [SDOI2012] Longge的问题

把2除到左边去就能生成所有毕达哥拉斯三元数了......给个推导: 令, 则 于是为完全平方数.

由于互质, 所以它们都是完全平方数. 令, 则

其中. 枚举, 再枚举, 验证是否为完全平方数, 其算术平方根是否与互质.

由上述推导可知, 以上公式生成了所有毕达哥拉斯三元数, 那么会不会重复呢?

把除到左边去, 得到. 在的假设下, 可以证明它们两两互质. 所以是三边的最大公约数, 即每个直角三角形是作为某个 "基本" 直角三角形的相似三角形来统计的, 是相似比.

易知是方程的两正根, 且根据假设, , 即, 如果某 "基本" 直角三角形对应一组, 那么这种对应是唯一的.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
	return b ? gcd(b, a%b) : a;
}

ll solve(ll r)
{
	ll ans = 0;
	for (ll i = 1; i*i < r/2; ++i) {
		ll j = floor(sqrt(r-i*i) + 0.5);
		ans += i*i + j*j == r && gcd(i, j) == 1;
	}
	return ans;
}

int main()
{
	ll n, ans = 0;
	scanf("%lld", &n);
	for (ll i = 1; i*i <= 2*n; ++i)
		if (2*n % i == 0)
			ans += solve(i) + (i*i == 2*n ? 0 : solve(2*n/i));
	printf("%lld\n", (ans+1)*4);
	return 0;
}