原文链接: https://leetcode-cn.com/problems/count-square-sum-triples

英文原文

A square triple (a,b,c) is a triple where a, b, and c are integers and a2 + b2 = c2.

Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.

 

Example 1:

Input: n = 5
Output: 2
Explanation: The square triples are (3,4,5) and (4,3,5).

Example 2:

Input: n = 10
Output: 4
Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).

 

Constraints:

• 1 <= n <= 250

中文题目

一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 a，b 和 c 。

给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。

 

示例 1：

输入：n = 5
输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。

示例 2：

输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。

 

提示：

• 1 <= n <= 250

通过代码

高赞题解

首先给出一个$O(n)$的算法。根据wiki - Pythagorean_triple，平方和三元组$(a,b,c)$可以由数对$(i,j)$用以下公式生成：
$a=k\cdot (j^2-i^2)$, $b=k\cdot (2ij)$, $c=k\cdot (i^2+j^2)$，
其中$i<j$, $(i,j)$互质且不同时为奇数。那么只要在$[\sqrt{n}]$的范围内枚举$i,j$即可(因为$i^2+j^2\leq n$)，满足条件的数对$(i,j)$会对答案产生$\dfrac{n}{i^2+j^2}$的贡献(即$k$的数量)，总复杂度$O(n)$。

class Solution {
public:
	int countTriples(int n) {
		int ans=0;
		for (int i=1;i*i<n;++i)
			for (int j=i+1;i*i+j*j<=n;++j)
				if (__gcd(i,j)==1&&!(i*j%2))ans+=n/(i*i+j*j);
		return ans*2;
	}
};

注：这里gcd的$O(\log n)$复杂度可以被消掉。

接下来使用更快的计数算法来加速。首先如果不考虑$k$的部分，那么满足条件的数对$(i,j)$的数量大致为$\sum_{1\leq j\leq \sqrt{n}}\phi(\min{\sqrt{n-j^2},j-1},j)$，其中$\phi(m,n)$表示$1,\dots,m$中与$n$互质的数的个数(暂时忽略“不同时为奇数”的限制条件，这个容易处理)。$\phi(m,n)$可以用容斥原理在$O(\sigma(n))$的时间内求出，其中$\sigma(n)$表示$n$的因子个数。
然后考虑$k$的部分。对于固定的$j$，$i$的取值可以在$[1,j]$内被分成若干个区间，每段区间共用同一个$k$的个数(因为$k$的上限为$\lfloor\dfrac{n}{i^2+j^2}\rfloor$)。那么只要用之前提到的容斥算法算出区间内与$j$互质的$i$的数量，再乘上这些$i$共用的$k$的上限值就行了。对于$j\leq n^{1/3}$，可行的$i$显然只有$\leq j=O(n^{1/3})$种。对于$j>n^{1/3}$，$\lfloor\dfrac{n}{i^2+j^2}\rfloor$的取值范围只有$O(\dfrac{n}{j^2})$种可能，所以$i$的范围可以被分成$O(\dfrac{n}{j^2})$段。对于所有$j$求和，总段数为$O(n^{1/3})\cdot O(n^{1/3})+\sum_{n^{1/3}\leq j\leq n^{1/2}}O(\dfrac{n}{j^2})=O(n^{2/3})$。
$\sigma(n)$在$1$~$n$内的平均值是$O(\log n)$量级的，所以总复杂度为$O(n^{2/3} \log n)$。

统计信息

通过次数	提交次数	AC比率
5459	7895	69.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言