一个 平方和三元组 (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)$。
思路与算法
我们可以枚举整数三元组 $(a, b, c)$ 中的 $a$ 和 $b$，并判断 $a^2 + b^2$ 是否为完全平方数，且 $\sqrt{a^2 + b^2}$ 是否为不大于 $n$ 的整数。
我们可以对 $a^2 + b^2$ 开平方，计算 $\left\lfloor \sqrt{a^2 + b^2} \right\rfloor^2$ 是否等于 $a^2 + b^2$ 以判断 $a^2 + b^2$ 是为完全平方数。同时，我们还需要判断 $\left\lfloor \sqrt{a^2 + b^2} \right\rfloor$ 是否不大于 $n$。
在遍历枚举的同时，我们维护平方和三元组的数目，如果符合要求，我们将计数加 $1$。最终，我们返回该数目作为答案。
细节
在计算 $\left\lfloor \sqrt{a^2 + b^2} \right\rfloor$ 时，为了防止浮点数造成的潜在误差，同时考虑到完全平方正数之间的距离一定大于 $1$，的我们可以用 $\sqrt{a^2 + b^2 + 1}$ 来替代 $\sqrt{a^2 + b^2}$。
代码
###C++
class Solution {
public:
int countTriples(int n) {
int res = 0;
// 枚举 a 与 b
for (int a = 1; a <= n; ++a){
for (int b = 1; b <= n; ++b){
// 判断是否符合要求
int c = int(sqrt(a * a + b * b + 1.0));
if (c <= n && c * c == a * a + b * b){
++res;
}
}
}
return res;
}
};
###Python
from math import sqrt
class Solution:
def countTriples(self, n: int) -> int:
res = 0
# 枚举 a 与 b
for a in range(1, n + 1):
for b in range(1, n + 1):
# 判断是否符合要求
c = int(sqrt(a ** 2 + b ** 2 + 1))
if c <= n and c ** 2 == a ** 2 + b ** 2:
res += 1
return res
###Java
class Solution {
public int countTriples(int n) {
int res = 0;
// 枚举 a 与 b
for (int a = 1; a <= n; ++a) {
for (int b = 1; b <= n; ++b) {
// 判断是否符合要求
int c = (int) Math.sqrt(a * a + b * b + 1.0);
if (c <= n && c * c == a * a + b * b) {
++res;
}
}
}
return res;
}
}
###C#
public class Solution {
public int CountTriples(int n) {
int res = 0;
// 枚举 a 与 b
for (int a = 1; a <= n; ++a) {
for (int b = 1; b <= n; ++b) {
// 判断是否符合要求
int c = (int) Math.Sqrt(a * a + b * b + 1.0);
if (c <= n && c * c == a * a + b * b) {
++res;
}
}
}
return res;
}
}
###Go
func countTriples(n int) int {
res := 0
// 枚举 a 与 b
for a := 1; a <= n; a++ {
for b := 1; b <= n; b++ {
// 判断是否符合要求
c := int(math.Sqrt(float64(a * a + b * b + 1)))
if c <= n && c * c == a * a + b * b {
res++
}
}
}
return res
}
###C
int countTriples(int n) {
int res = 0;
// 枚举 a 与 b
for (int a = 1; a <= n; ++a) {
for (int b = 1; b <= n; ++b) {
// 判断是否符合要求
int c = (int) sqrt(a * a + b * b + 1.0);
if (c <= n && c * c == a * a + b * b) {
++res;
}
}
}
return res;
}
###JavaScript
var countTriples = function(n) {
let res = 0;
// 枚举 a 与 b
for (let a = 1; a <= n; a++) {
for (let b = 1; b <= n; b++) {
// 判断是否符合要求
let c = Math.floor(Math.sqrt(a * a + b * b + 1));
if (c <= n && c * c === a * a + b * b) {
res++;
}
}
}
return res;
};
###TypeScript
function countTriples(n: number): number {
let res = 0;
// 枚举 a 与 b
for (let a = 1; a <= n; a++) {
for (let b = 1; b <= n; b++) {
// 判断是否符合要求
let c = Math.floor(Math.sqrt(a * a + b * b + 1));
if (c <= n && c * c === a * a + b * b) {
res++;
}
}
}
return res;
};
###Rust
impl Solution {
pub fn count_triples(n: i32) -> i32 {
let mut res = 0;
// 枚举 a 与 b
for a in 1..= n {
for b in 1..= n {
// 判断是否符合要求
let c = ((a * a + b * b) as f64).sqrt().floor() as i32;
if c <= n && c * c == a * a + b * b {
res += 1;
}
}
}
res
}
}
复杂度分析
时间复杂度：$O(n^2)$，其中 $n$ 为三元组元素的上界。即为遍历 $a$ 与 $b$ 的时间复杂度。
空间复杂度：$O(1)$。
先说暴力怎么做。
我们可以枚举所有 $a>b$ 的平方和三元组 $(a,b,c)$。由于 $a^2+b^2=b^2+a^2$，所以 $(b,a,c)$ 也是平方和三元组。所以只需统计 $a>b$ 的情况，最后把统计结果乘以 $2$，即为答案。
$a=b$ 的情况呢？如果 $2a^2 = c^2$，那么 $c = \sqrt 2 a$，所以 $c$ 一定不是整数（反证法：如果 $c$ 是整数，式子变形得 $\dfrac{c}{a} = \sqrt 2$，左边是有理数，右边是无理数，有理数不可能等于无理数）。所以无需考虑 $a=b$ 的情况。
枚举 $a=2,3,\ldots,n-1$，枚举 $b=1,2,\ldots,a-1$，如果 $a^2+b^2\le n$ 且 $c = \sqrt{a^2+b^2}$ 是整数，那么我们找到了一个平方和三元组 $(a,b,c)$，计数器加一。
class Solution:
def countTriples(self, n: int) -> int:
ans = 0
for a in range(1, n):
for b in range(1, a):
if a * a + b * b > n * n:
break
c2 = a * a + b * b
if isqrt(c2) ** 2 == c2:
ans += 1
return ans * 2 # (a,b,c) 和 (b,a,c) 各算一次
class Solution {
public int countTriples(int n) {
int ans = 0;
for (int a = 1; a < n; a++) {
for (int b = 1; b < a && a * a + b * b <= n * n; b++) {
int c2 = a * a + b * b;
int rt = (int) Math.sqrt(c2);
if (rt * rt == c2) {
ans++;
}
}
}
return ans * 2; // (a,b,c) 和 (b,a,c) 各算一次
}
}
class Solution {
public:
int countTriples(int n) {
int ans = 0;
for (int a = 1; a < n; a++) {
for (int b = 1; b < a && a * a + b * b <= n * n; b++) {
int c2 = a * a + b * b;
int rt = sqrt(c2);
if (rt * rt == c2) {
ans++;
}
}
}
return ans * 2; // (a,b,c) 和 (b,a,c) 各算一次
}
};
func countTriples(n int) (ans int) {
for a := 1; a < n; a++ {
for b := 1; b < a && a*a+b*b <= n*n; b++ {
c2 := a*a + b*b
rt := int(math.Sqrt(float64(c2)))
if rt*rt == c2 {
ans++
}
}
}
return ans * 2 // (a,b,c) 和 (b,a,c) 各算一次
}
请看 勾三股四弦五：生成勾股数的公式。
class Solution:
def countTriples(self, n: int) -> int:
ans = 0
u = 3
while u * u < n * 2:
v = 1
while v < u and u * u + v * v <= n * 2:
if gcd(u, v) == 1:
ans += n * 2 // (u * u + v * v)
v += 2
u += 2
return ans * 2 # (a,b,c) 和 (b,a,c) 各算一次
MX = isqrt(500) + 1
gcds = [[0] * MX for _ in range(MX)]
for i in range(1, MX):
gcds[i][0] = i
for j in range(1, MX):
# 更相减损术
gcds[i][j] = gcds[i][j - i] if j >= i else gcds[j][i]
class Solution:
def countTriples(self, n: int) -> int:
ans = 0
u = 3
while u * u < n * 2:
v = 1
while v < u and u * u + v * v <= n * 2:
if gcds[u][v] == 1:
ans += n * 2 // (u * u + v * v)
v += 2
u += 2
return ans * 2 # (a,b,c) 和 (b,a,c) 各算一次
class Solution {
public int countTriples(int n) {
int ans = 0;
for (int u = 3; u * u < n * 2; u += 2) {
for (int v = 1; v < u && u * u + v * v <= n * 2; v += 2) {
if (gcd(u, v) == 1) {
ans += n * 2 / (u * u + v * v);
}
}
}
return ans * 2; // (a,b,c) 和 (b,a,c) 各算一次
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
class Solution {
public:
int countTriples(int n) {
int ans = 0;
for (int u = 3; u * u < n * 2; u += 2) {
for (int v = 1; v < u && u * u + v * v <= n * 2; v += 2) {
if (gcd(u, v) == 1) {
ans += n * 2 / (u * u + v * v);
}
}
}
return ans * 2; // (a,b,c) 和 (b,a,c) 各算一次
}
};
func countTriples(n int) (ans int) {
for u := 3; u*u < n*2; u += 2 {
for v := 1; v < u && u*u+v*v <= n*2; v += 2 {
if gcd(u, v) == 1 {
ans += n * 2 / (u*u + v*v)
}
}
}
return ans * 2 // (a,b,c) 和 (b,a,c) 各算一次
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
更仔细地考察枚举 $(u,v)$ 计算 $\left\lfloor\dfrac{2n}{u^2+v^2}\right\rfloor$ 的过程：
推荐读者先看 数论分块 中的图，先理解怎么算 $\displaystyle\sum_{i=1}^{n} \left\lfloor\dfrac{n}{i}\right\rfloor$，再理解更复杂的 $\left\lfloor\dfrac{2n}{u^2+v^2}\right\rfloor$。
外层循环枚举 $u=3,5,7,\ldots$ 内层循环用数论分块枚举 $v$。
设闭区间 $[L,R]$ 内的 $v$，对应的 $\left\lfloor\dfrac{2n}{u^2+v^2}\right\rfloor$ 都相等。
如果已知 $L$，如何计算 $R$？一开始 $L=1$，只要我们算出了 $R$，那么下一个区间的左端点 $L'$ 就是 $R+1$。再用同样的方法根据 $L'$ 算出 $R'$，得到下下个区间的左端点 $L'' = R'+1$，依此类推，用这个方法可以算出后续所有区间。
设 $\textit{num} = \left\lfloor\dfrac{2n}{u^2+L^2}\right\rfloor$。
由于 $\dfrac{2n}{u^2+v^2}$ 的整数部分是 $\textit{num}$，即
$$
\dfrac{2n}{u^2+v^2}\ge \textit{num}
$$
所以
$$
(u^2+v^2)\cdot \textit{num}\le 2n
$$
在正整数情况下，上式等价于
$$
u^2+v^2\le \left\lfloor\dfrac{2n}{\textit{num}}\right\rfloor
$$
解得
$$
v\le \sqrt{\left\lfloor\dfrac{2n}{\textit{num}}\right\rfloor - u^2}
$$
由于 $v < u$，所以还要与 $u-1$ 取最小值，得到
$$
R = \min\left(\sqrt{\left\lfloor\dfrac{2n}{\textit{num}}\right\rfloor - u^2},u-1\right)
$$
对于 $[L,R]$ 内的 $v$，还要满足 $v$ 是奇数，且 $v$ 与 $u$ 互质。
现在问题变成：
用 $[1,R]$ 的答案，减去 $[1,L-1]$ 的答案，就是 $[L,R]$ 的答案。
$[1,R]$ 内的与 $u$ 互质的奇数个数，等于 $[1,R]$ 内的与 $u$ 互质的整数个数，减去 $[1,R]$ 内的与 $u$ 互质的偶数个数。对于后者，设偶数为 $2k$，由于 $u$ 是奇数（不含质因子 $2$），所以 $\gcd(2k,u) = \gcd(k,u)$，我们只需考虑 $k$ 与 $u$ 是否互质。由于 $2k\le R$，所以 $k\le \lfloor\frac{R}{2}\rfloor$。所以 $[1,R]$ 内的与 $u$ 互质的偶数个数，等于 $[1,\lfloor\frac{R}{2}\rfloor]$ 内的与 $u$ 互质的整数个数。
设 $n$ 以内的与 $u$ 互质的正整数个数为 $f(n,u)$。那么 $[1,R]$ 的答案就是 $f(R,u) - f(\lfloor\frac{R}{2}\rfloor, u)$。
计算 $n$ 以内的与 $u$ 互质的正整数个数 $f(n,u)$。
例如 $u=15$。与 $15$ 互质的数，不能包含质因子 $3$ 和 $5$。
所以
$$
f(n,15) = n - \left\lfloor\dfrac{n}{3}\right\rfloor - \left\lfloor\dfrac{n}{5}\right\rfloor + \left\lfloor\dfrac{n}{15}\right\rfloor
$$
一般地，设 $u$ 的质因子集合为 $P$，由容斥原理可得
$$
f(n,u) = \sum_{S\subseteq P} (-1)^{|S|} \left\lfloor\dfrac{n}{\prod S}\right\rfloor
$$
用莫比乌斯函数表示就是
$$
f(n,u) = \sum_{d|u} \mu(d) \left\lfloor\dfrac{n}{d}\right\rfloor
$$
其中莫比乌斯函数为
$$
\mu(n)=
\begin{cases}
1, & n=1\
(-1)^k, & n = p_1p_2\dots p_k\
0, & n\ 有大于\ 1\ 的平方因子
\end{cases}
$$
注：也可以用莫比乌斯反演推导 $f(n,u)$ 的式子。
MX = isqrt(500) + 1
# 预处理莫比乌斯函数
# 当 n > 1 时，sum_{d|n} mu[d] = 0
# 所以 mu[n] = -sum_{d|n ∧ d<n} mu[d]
mu = [0] * MX
mu[1] = 1
for i in range(1, MX):
for j in range(i * 2, MX, i):
mu[j] -= mu[i] # i 是 j 的真因子
# 预处理不含平方因子的因子列表，用于 count_coprime
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
if mu[i]:
for j in range(i, MX, i):
divisors[j].append(i) # i 是 j 的因子，且 mu[i] != 0
# 返回 [1,n] 中与 x 互质的整数个数
def count_coprime(n: int, x: int) -> int:
return sum(mu[d] * (n // d) for d in divisors[x])
# 返回 [1,n] 中与奇数 x 互质的奇数个数
# 与 x 互质的整数个数 - 与 x 互质的偶数个数
def count_coprime_odd(n: int, x: int) -> int:
return count_coprime(n, x) - count_coprime(n // 2, x)
class Solution:
def countTriples(self, n: int) -> int:
ans = 0
u = 3
while u * u < n * 2:
l = 1
while l < u and u * u + l * l <= n * 2:
num = (n * 2) // (u * u + l * l)
# 对于 [l,r] 中的整数 v，2n // (u^2 + v^2) 都等于 num
r = min(isqrt(n * 2 // num - u * u), u - 1) # 推导过程见题解
# 只有与 u 互质的奇数 v 才能得到本原勾股数组
num_coprime_odd_v = count_coprime_odd(r, u) - count_coprime_odd(l - 1, u)
ans += num * num_coprime_odd_v
l = r + 1
u += 2
return ans * 2 # (a,b,c) 和 (b,a,c) 各算一次
class Solution {
private static final int MX = 23; // floor(sqrt(250 * 2)) + 1
private static final int[] mu = new int[MX];
private static final List<Integer>[] divisors = new ArrayList[MX];
static {
// 预处理莫比乌斯函数
// 当 n > 1 时，sum_{d|n} mu[d] = 0
// 所以 mu[n] = -sum_{d|n ∧ d<n} mu[d]
mu[1] = 1;
for (int i = 1; i < MX; i++) {
for (int j = i * 2; j < MX; j += i) {
mu[j] -= mu[i]; // i 是 j 的真因子
}
}
// 预处理不含平方因子的因子列表，用于 countCoprime
Arrays.setAll(divisors, _ -> new ArrayList<>());
for (int i = 1; i < MX; i++) {
if (mu[i] == 0) {
continue;
}
for (int j = i; j < MX; j += i) {
divisors[j].add(i); // i 是 j 的因子，且 mu[i] != 0
}
}
}
public int countTriples(int n) {
int ans = 0;
for (int u = 3; u * u < n * 2; u += 2) {
for (int l = 1, r; l < u && u * u + l * l <= n * 2; l = r + 1) {
int num = (n * 2) / (u * u + l * l);
// 对于 [l,r] 中的整数 v，floor(2n / (u^2 + v^2)) 都等于 num
r = Math.min((int) Math.sqrt(n * 2 / num - u * u), u - 1); // 推导过程见题解
// 只有与 u 互质的奇数 v 才能得到本原勾股数组
int numCoprimeOddV = countCoprimeOdd(r, u) - countCoprimeOdd(l - 1, u);
ans += num * numCoprimeOddV;
}
}
return ans * 2; // (a,b,c) 和 (b,a,c) 各算一次
}
// 返回 [1,n] 中与奇数 x 互质的奇数个数
// 与 x 互质的整数个数 - 与 x 互质的偶数个数
private int countCoprimeOdd(int n, int x) {
return countCoprime(n, x) - countCoprime(n / 2, x);
}
// 返回 [1,n] 中与 x 互质的整数个数
private int countCoprime(int n, int x) {
int res = 0;
for (int d : divisors[x]) {
res += mu[d] * (n / d);
}
return res;
}
}
constexpr int MX = 23; // floor(sqrt(250 * 2)) + 1
int mu[MX];
vector<int> divisors[MX];
int init = [] {
// 预处理莫比乌斯函数
// 当 n > 1 时，sum_{d|n} mu[d] = 0
// 所以 mu[n] = -sum_{d|n ∧ d<n} mu[d]
mu[1] = 1;
for (int i = 1; i < MX; i++) {
for (int j = i * 2; j < MX; j += i) {
mu[j] -= mu[i]; // i 是 j 的真因子
}
}
// 预处理不含平方因子的因子列表，用于 count_coprime
for (int i = 1; i < MX; i++) {
if (mu[i]) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i); // i 是 j 的因子，且 mu[i] != 0
}
}
}
return 0;
}();
class Solution {
// 返回 [1,n] 中与 x 互质的整数个数
int count_coprime(int n, int x) {
int res = 0;
for (int d : divisors[x]) {
res += mu[d] * (n / d);
}
return res;
}
// 返回 [1,n] 中与奇数 x 互质的奇数个数
// 与 x 互质的整数个数 - 与 x 互质的偶数个数
int count_coprime_odd(int n, int x) {
return count_coprime(n, x) - count_coprime(n / 2, x);
}
public:
int countTriples(int n) {
int ans = 0;
for (int u = 3; u * u < n * 2; u += 2) {
for (int l = 1, r; l < u && u * u + l * l <= n * 2; l = r + 1) {
int num = (n * 2) / (u * u + l * l);
// 对于 [l,r] 中的整数 v，floor(2n / (u^2 + v^2)) 都等于 num
r = min((int) sqrt(n * 2 / num - u * u), u - 1); // 推导过程见题解
// 只有与 u 互质的奇数 v 才能得到本原勾股数组
int num_coprime_odd_v = count_coprime_odd(r, u) - count_coprime_odd(l - 1, u);
ans += num * num_coprime_odd_v;
}
}
return ans * 2; // (a,b,c) 和 (b,a,c) 各算一次
}
};
const mx = 23 // floor(sqrt(250 * 2)) + 1
var mu = [mx]int{1: 1}
var divisors [mx][]int
func init() {
// 预处理莫比乌斯函数
// 当 n > 1 时，sum_{d|n} mu[d] = 0
// 所以 mu[n] = -sum_{d|n ∧ d<n} mu[d]
for i := 1; i < mx; i++ {
for j := i * 2; j < mx; j += i {
mu[j] -= mu[i] // i 是 j 的真因子
}
}
// 预处理不含平方因子的因子列表，用于 countCoprime
for i := 1; i < mx; i++ {
if mu[i] == 0 {
continue
}
for j := i; j < mx; j += i {
divisors[j] = append(divisors[j], i) // i 是 j 的因子，且 mu[i] != 0
}
}
}
// 返回 [1,n] 中与 x 互质的整数个数
func countCoprime(n, x int) (res int) {
for _, d := range divisors[x] {
res += mu[d] * (n / d)
}
return
}
// 返回 [1,n] 中与奇数 x 互质的奇数个数
// 与 x 互质的整数个数 - 与 x 互质的偶数个数
func countCoprimeOdd(n, x int) (res int) {
return countCoprime(n, x) - countCoprime(n/2, x)
}
func countTriples(n int) (ans int) {
for u := 3; u*u < n*2; u += 2 {
for l, r := 1, 0; l < u && u*u+l*l <= n*2; l = r + 1 {
num := n * 2 / (u*u + l*l)
// 对于 [l,r] 中的整数 v，floor(2n / (u^2 + v^2)) 都等于 num
r = min(int(math.Sqrt(float64(n*2/num-u*u))), u-1) // 推导过程见题解
// 只有与 u 互质的奇数 v 才能得到本原勾股数组
numCoprimeOddV := countCoprimeOdd(r, u) - countCoprimeOdd(l-1, u)
ans += num * numCoprimeOddV
}
}
return ans * 2 // (a,b,c) 和 (b,a,c) 各算一次
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
预处理的时空复杂度为 $\mathcal{O}(\sqrt N\log N)$，$N=500$，不计入。
注：进一步地，考虑根号分解，取阈值 $B = \sqrt[3] {n\ln n} $，当 $u\le B$ 时使用方法二，当 $u>B$ 时使用方法三，可以做到 $\mathcal{O}\left((n\log n)^{2/3}\right)$ 的时间复杂度。
欢迎关注 B站@灵茶山艾府
给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。
示例 1：
输入：low = 3, high = 7 输出：3 解释：3 到 7 之间奇数数字为 [3,5,7] 。
示例 2：
输入：low = 8, high = 10 输出：1 解释：8 到 10 之间奇数数字为 [9] 。
提示：
0 <= low <= high <= 10^9$[\textit{low},\textit{high}]$ 中的正奇数个数，等于 $[1,\textit{high}]$ 中的正奇数个数，减去 $[1,\textit{low}-1]$ 中的正奇数个数。（这个想法类似 前缀和）
正奇数可以表示为 $2k-1$，其中 $k$ 是正整数。
$[1,n]$ 中的正奇数满足 $1\le 2k-1\le n$，解得
$$
1\le k \le \left\lfloor\dfrac{n+1}{2}\right\rfloor
$$
这有 $\left\lfloor\dfrac{n+1}{2}\right\rfloor$ 个整数 $k$。
所以答案为
$$
\left\lfloor\dfrac{\textit{high}+1}{2}\right\rfloor - \left\lfloor\dfrac{\textit{low}}{2}\right\rfloor
$$
###py
class Solution:
def countOdds(self, low: int, high: int) -> int:
return (high + 1) // 2 - low // 2
###java
class Solution {
public int countOdds(int low, int high) {
return (high + 1) / 2 - low / 2;
}
}
###cpp
class Solution {
public:
int countOdds(int low, int high) {
return (high + 1) / 2 - low / 2;
}
};
###c
int countOdds(int low, int high) {
return (high + 1) / 2 - low / 2;
}
###go
func countOdds(low, high int) int {
return (high+1)/2 - low/2
}
###js
var countOdds = function(low, high) {
return Math.floor((high + 1) / 2) - Math.floor(low / 2);
};
###rust
impl Solution {
pub fn count_odds(low: i32, high: i32) -> i32 {
(high + 1) / 2 - low / 2
}
}
欢迎在评论区分享你的思路/代码。
欢迎关注 B站@灵茶山艾府
假设一个区间【0，3】，序列是0,1,2,3 奇数个数是3+1/2=2，区间【0,4】，序列是0,1,2,3,4 奇数个数4+1/2=2。
所以，所以，所以，high为3或者4，加个1，然后除以2，奇数个数都是2，然后，请自己推【0,5】和【0,6】，奇数个数都是3。
得出公式 high+1/2是区间【0，high】的奇数个数
因为low，左边界是可以改变的，所以先求【0，high】的奇数个数，然后在求【0，low】的奇数个数，然后做差得到总奇数个数。
注意，注意，注意，把+1看成右边区间增大，这里low是相当于在【0，high】里面的，你别加1，右边界high增大就行了。
**举个例子：**区间【3,7】，high的奇数个数 7+1/2=4,，如果此时3+1/2=2,4-2=2，答案就错了，要3/2=1，最后答案才等于3。
high+1奇数个数 - low奇数个数 **=**总奇数个数。
用公式表示 (high+1)/2 - low/2
int countOdds(int low, int high){
return ((high+1)/2)-((low)/2); //严谨
}
思路与算法
如果我们暴力枚举 ${\rm [low, high]}$ 中的所有元素会超出时间限制。
我们可以使用前缀和思想来解决这个问题，定义 ${\rm pre}(x)$ 为区间 $[0, x]$ 中奇数的个数，很显然：
$${\rm pre}(x) = \lfloor \frac{x + 1}{2} \rfloor$$
故答案为 $\rm pre(high) - pre(low - 1)$。
代码
###C++
class Solution {
public:
int pre(int x) {
return (x + 1) >> 1;
}
int countOdds(int low, int high) {
return pre(high) - pre(low - 1);
}
};
###Java
class Solution {
public int countOdds(int low, int high) {
return pre(high) - pre(low - 1);
}
public int pre(int x) {
return (x + 1) >> 1;
}
}
###Python
class Solution:
def countOdds(self, low: int, high: int) -> int:
pre = lambda x: (x + 1) >> 1
return pre(high) - pre(low - 1)
###C#
public class Solution {
public int Pre(int x) {
return (x + 1) >> 1;
}
public int CountOdds(int low, int high) {
return Pre(high) - Pre(low - 1);
}
}
###Go
func pre(x int) int {
return (x + 1) >> 1
}
func countOdds(low int, high int) int {
return pre(high) - pre(low - 1)
}
###C
int pre(int x) {
return (x + 1) >> 1;
}
int countOdds(int low, int high) {
return pre(high) - pre(low - 1);
}
###JavaScript
var countOdds = function(low, high) {
return pre(high) - pre(low - 1);
};
function pre(x) {
return (x + 1) >> 1;
}
###TypeScript
function pre(x: number): number {
return (x + 1) >> 1;
}
function countOdds(low: number, high: number): number {
return pre(high) - pre(low - 1);
}
###Rust
impl Solution {
fn pre(x: i32) -> i32 {
(x + 1) >> 1
}
pub fn count_odds(low: i32, high: i32) -> i32 {
Self::pre(high) - Self::pre(low - 1)
}
}
复杂度分析
时间复杂度：$O(1)$。
空间复杂度：$O(1)$。
给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。
返回在此条件下将 nums 分割的总方法数。
由于答案可能非常大，返回结果需要对 109 + 7 取余数。
示例 1：
输入： nums = [9,4,1,3,7], k = 4
输出： 6
解释：
共有 6 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 k = 4：
[[9], [4], [1], [3], [7]][[9], [4], [1], [3, 7]][[9], [4], [1, 3], [7]][[9], [4, 1], [3], [7]][[9], [4, 1], [3, 7]][[9], [4, 1, 3], [7]]示例 2：
输入： nums = [3,3,4], k = 0
输出： 2
解释：
共有 2 种有效的分割方式，满足给定条件：
[[3], [3], [4]][[3, 3], [4]]
提示：
2 <= nums.length <= 5 * 1041 <= nums[i] <= 1090 <= k <= 109本题是标准的划分型 DP，见 DP 题单 的「§5.2 最优划分」。
一般定义 $f[i+1]$ 表示前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 在题目约束下，分割出的最少（最多）子数组个数，本题是定义成分割方案数。这里 $i+1$ 是为了把 $f[0]$ 当作初始值。
枚举最后一个子数组的左端点 $j$，那么问题变成前缀 $\textit{nums}[0]$ 到 $\textit{nums}[j-1]$ 在题目约束下的分割方案数，即 $f[j]$。
当子数组右端点 $i$ 固定时，由于子数组越长，最大值越大，最小值越小，最大最小的差值越可能大于 $k$。所以符合要求的左端点 $j$ 一定在一个连续区间 $[L,i]$ 中。累加 $f[j]$ 得
$$
f[i+1] = \sum_{j=L}^{i} f[j]
$$
初始值 $f[0] = 1$，空子数组算一个方案。也可以从递归的角度理解，递归到空子数组，就表示我们找到了一个合法分割方案。
答案为 $f[n]$。
由于 $i$ 越大，$L$ 也越大，可以用 滑动窗口【基础算法精讲 03】。
同时，我们需要计算 239. 滑动窗口最大值 和滑动窗口最小值，这可以用 单调队列【基础算法精讲 27】解决。
维护窗口中的 $\displaystyle\sum_{j=L}^{i} f[j]$，记作 $\textit{sumF}$，转移方程优化成
$$
f[i+1] = \textit{sumF}
$$
注意取模。关于模运算的知识点，见 模运算的世界：当加减乘除遇上取模。
本题视频讲解，欢迎点赞关注~
###py
class Solution:
def countPartitions(self, nums: List[int], k: int) -> int:
MOD = 1_000_000_007
n = len(nums)
min_q = deque()
max_q = deque()
f = [0] * (n + 1)
f[0] = 1
sum_f = 0 # 窗口中的 f[i] 之和
left = 0
for i, x in enumerate(nums):
# 1. 入
sum_f += f[i]
while min_q and x <= nums[min_q[-1]]:
min_q.pop()
min_q.append(i)
while max_q and x >= nums[max_q[-1]]:
max_q.pop()
max_q.append(i)
# 2. 出
while nums[max_q[0]] - nums[min_q[0]] > k:
sum_f -= f[left]
left += 1
if min_q[0] < left:
min_q.popleft()
if max_q[0] < left:
max_q.popleft()
# 3. 更新答案
f[i + 1] = sum_f % MOD
return f[n]
###java
class Solution {
public int countPartitions(int[] nums, int k) {
final int MOD = 1_000_000_007;
int n = nums.length;
Deque<Integer> minQ = new ArrayDeque<>(); // 更快的写法见【Java 数组】
Deque<Integer> maxQ = new ArrayDeque<>();
int[] f = new int[n + 1];
f[0] = 1;
long sumF = 0; // 窗口中的 f[i] 之和
int left = 0;
for (int i = 0; i < n; i++) {
// 1. 入
sumF += f[i];
int x = nums[i];
while (!minQ.isEmpty() && x <= nums[minQ.peekLast()]) {
minQ.pollLast();
}
minQ.addLast(i);
while (!maxQ.isEmpty() && x >= nums[maxQ.peekLast()]) {
maxQ.pollLast();
}
maxQ.addLast(i);
// 2. 出
while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > k) {
sumF -= f[left];
left++;
if (minQ.peekFirst() < left) {
minQ.pollFirst();
}
if (maxQ.peekFirst() < left) {
maxQ.pollFirst();
}
}
// 3. 更新答案
f[i + 1] = (int) (sumF % MOD);
}
return f[n];
}
}
###java
class Solution {
public int countPartitions(int[] nums, int k) {
final int MOD = 1_000_000_007;
int n = nums.length;
int[] minQ = new int[n];
int[] maxQ = new int[n];
int minHead = 0, minTail = -1;
int maxHead = 0, maxTail = -1;
int[] f = new int[n + 1];
f[0] = 1;
long sumF = 0; // 窗口中的 f[i] 之和
int left = 0;
for (int i = 0; i < n; i++) {
// 1. 入
sumF += f[i];
int x = nums[i];
while (minHead <= minTail && x <= nums[minQ[minTail]]) {
minTail--;
}
minQ[++minTail] = i;
while (maxHead <= maxTail && x >= nums[maxQ[maxTail]]) {
maxTail--;
}
maxQ[++maxTail] = i;
// 2. 出
while (nums[maxQ[maxHead]] - nums[minQ[minHead]] > k) {
sumF -= f[left];
left++;
if (minQ[minHead] < left) {
minHead++;
}
if (maxQ[maxHead] < left) {
maxHead++;
}
}
// 3. 更新答案
f[i + 1] = (int) (sumF % MOD);
}
return f[n];
}
}
###cpp
class Solution {
public:
int countPartitions(vector<int>& nums, int k) {
const int MOD = 1'000'000'007;
int n = nums.size();
deque<int> min_q, max_q;
vector<int> f(n + 1);
f[0] = 1;
long long sum_f = 0; // 窗口中的 f[i] 之和
int left = 0;
for (int i = 0; i < n; i++) {
int x = nums[i];
// 1. 入
sum_f += f[i];
while (!min_q.empty() && x <= nums[min_q.back()]) {
min_q.pop_back();
}
min_q.push_back(i);
while (!max_q.empty() && x >= nums[max_q.back()]) {
max_q.pop_back();
}
max_q.push_back(i);
// 2. 出
while (nums[max_q.front()] - nums[min_q.front()] > k) {
sum_f -= f[left];
left++;
if (min_q.front() < left) {
min_q.pop_front();
}
if (max_q.front() < left) {
max_q.pop_front();
}
}
// 3. 更新答案
f[i + 1] = sum_f % MOD;
}
return f[n];
}
};
###go
func countPartitions(nums []int, k int) int {
const mod = 1_000_000_007
n := len(nums)
var minQ, maxQ []int
f := make([]int, n+1)
f[0] = 1
sumF := 0 // 窗口中的 f[i] 之和
left := 0
for i, x := range nums {
// 1. 入
sumF += f[i]
for len(minQ) > 0 && x <= nums[minQ[len(minQ)-1]] {
minQ = minQ[:len(minQ)-1]
}
minQ = append(minQ, i)
for len(maxQ) > 0 && x >= nums[maxQ[len(maxQ)-1]] {
maxQ = maxQ[:len(maxQ)-1]
}
maxQ = append(maxQ, i)
// 2. 出
for nums[maxQ[0]]-nums[minQ[0]] > k {
sumF -= f[left]
left++
if minQ[0] < left {
minQ = minQ[1:]
}
if maxQ[0] < left {
maxQ = maxQ[1:]
}
}
// 3. 更新答案
f[i+1] = sumF % mod
}
return f[n]
}
更多相似题目，见下面动态规划题单的「§5.2 最优划分」和「§11.3 单调队列优化 DP」。
维护 $f(i)$ 表示前 $i$ 个元素的分割方案。转移时，枚举上一个子段的末尾在哪，有转移方程
$$
f(i) = \sum f(j)
$$
其中 $j$ 满足 $\max(a_{j + 1}, a_{j + 2}, \cdots, a_i) - \min(a_{j + 1}, a_{j + 2}, \cdots, a_i) \le k$
直接计算 DP 方程的复杂度为 $\mathcal{O}(n^2)$，还需要进一步观察合法的 $j$ 有什么特征。
注意到，如果某个子数组的极值之差小于等于 $k$，那么它的子数组的极值之差也小于等于 $k$。这是典型的双指针特征，因此合法的 $j$ 就是一段连续值，从某个值一直取到 $(i - 1)$。用双指针算出最小的合法 $j$，再用前缀和计算区间和即可。复杂度 $\mathcal{O}(n\log n)$，这里的 $\log n$ 主要是我们需要用数据结构（比如 multiset）动态维护滑动窗口里的最小值和最大值。
class Solution {
public:
int countPartitions(vector<int>& nums, int K) {
int n = nums.size();
const int MOD = 1e9 + 7;
// f[i]：前 i 个元素的分割方案数
// g[i]：f 的前缀和
long long f[n + 1], g[n + 1];
f[0] = g[0] = 1;
// 用 multiset 记录滑动窗口里的数，方便求出最小值和最大值
multiset<int> ms;
// 枚举双指针的右端点 i，计算合法子段左端点的最小值 j
for (int i = 1, j = 1; i <= n; i++) {
ms.insert(nums[i - 1]);
while (j < i && *prev(ms.end()) - *ms.begin() > K) {
ms.erase(ms.find(nums[j - 1]));
j++;
}
// j 是最小的左端点
// 那么上一个子段最小的右端点就是 j - 1
// 前缀和就得减去 j - 2 的值
f[i] = (g[i - 1] - (j - 2 >= 0 ? g[j - 2] : 0) + MOD) % MOD;
g[i] = (g[i - 1] + f[i]) % MOD;
}
return f[n];
}
};
