题面

---

如果 $n\le10^9$，阁下该如何应对？

$O(n)$ 算法：

#include <cstdio>
int main() {
    int n, s; // 大数据要用long long
    scanf("%d", &n);
    for (int a = 1; a <= n; a++) s += (n - a + 1) >> (a & 1);
    printf("%d", s);
    return 0;
}

这是怎么来的？

题目要求计算有多少对正整数 $(a,b)$ 满足 $a,b\le n$ 且 $\dfrac{ab}2$ 为整数。

转化条件：当 $a$ 为奇数时，$b$ 为不超过 $n$ 的偶数；当 $a$ 为偶数时，$b$ 为不超过 $n$ 的正整数；$b\ge a$（不重复计数）。故答案为 $\displaystyle\sum_{a=1}^nf(a)$，其中

$$\begin{align*} f(a)&=\begin{cases}\left\lfloor\dfrac{n-a+1}2\right\rfloor,&a为奇数,\\[10pt]n-a+1,&a为偶数\end{cases}\\ &=\left\lfloor\dfrac{n-a+1}{2^{a\bmod2}}\right\rfloor. \end{align*}$$

这就是程序里的 (n - a + 1) >> (a & 1)。

---

$O(1)$ 算法：

#include <cstdio>
int main() {
    int n; // 大数据要用long long
    scanf("%d", &n);
    printf("%d", n & 1 ? (n * n - 1) * 3 >> 3 : n * (n * 3 + 2) >> 3);
    return 0;
}

这是怎么来的？

我们引入序号 $k$：

• 当 $a$ 为奇数时，将其表示为 $a=2k-1$，其中 $k\ge1$；
• 当 $a$ 为偶数时，将其表示为 $a=2k$，其中 $k\ge1$。

---

情况一：当 $n$ 为奇数时

设 $n=2m+1$（此时 $m=\dfrac{n-1}2$ 是整数），则奇数 $a$ 最大为 $2m+1$，对应 $k=m+1$；偶数 $a$ 最大为 $2m$，对应 $k=m$。

1. 计算奇数项 $S_{\rm odd}$

代入 $a=2k-1$，得 $n-a+1=(2m+1)-(2k-1)+1=2m-2k+3$。因为 $n$ 和 $a$ 是奇数，所以 $n-a+1$ 是奇数，故 $f(2k-1)=\dfrac{2m-2k+3-1}2=m-k+1$。
对 $k$ 从 $1$ 到 $m+1$ 求和，得 $\displaystyle S_{\rm odd}=\sum_{k=1}^{m+1}(m-k+1)=\sum_{k=1}^m(m-k+1)$。
令 $j=m-k+1$，当 $k$ 从 $1$ 到 $m$ 时，$j$ 从 $m$ 到 $1$，$\displaystyle S_{\rm odd}=\sum_{j=1}^mj=\frac{m(m+1)}2.$

2. 计算偶数项 $S_{\rm even}$

代入 $a=2k$，得 $f(2k)=n-2k+1=(2m+1)-2k+1=2m-2k+2=2(m-k+1)$。
对 $k$ 从 $1$ 到 $m$ 求和，得 $\displaystyle S_{\rm even}=\sum_{k=1}^m2(m-k+1)=2\sum_{j=1}^mj=2\cdot\frac{m(m+1)}2=m(m+1).$

3. 合并得到 $S$

$S=S_{\rm odd}+S_{\rm even}=\dfrac{m(m+1)}2+m(m+1)=\dfrac{3m(m+1)}2$，将 $m=\dfrac{n-1}2$ 代回得 $S=\dfrac{3\cdot\frac{n-1}2\cdot\frac{n+1}2}2=\dfrac{3(n-1)(n+1)}8=\dfrac{3(n^2-1)}8.$

---

情况二：当 $n$ 为偶数时

设 $n=2m$（此时 $m=\dfrac n2$ 是整数），则奇数 $a$ 最大为 $2m-1$，对应 $k=m$；偶数 $a$ 最大为 $2m$ ，对应 $k=m$。

1. 计算奇数项 $S_{\rm odd}$

代入 $a=2k-1$，得 $n-a+1=2m-(2k-1)+1=2m-2k+2=2(m-k+1)$。这是一个偶数，故 $f(2k-1)=\dfrac{2(m-k+1)}2=m-k+1$。

对 $k$ 从 $1$ 到 $m$ 求和，得 $\displaystyle S_{\rm odd}=\sum_{k=1}^m(m-k+1)=\sum_{j=1}^mj=\frac{m(m+1)}2.$

2. 计算偶数项 $S_{\rm even}$

代入 $a=2k$，得 $f(2k)=n-2k+1=2m-2k+1$。
对 $k$ 从 $1$ 到 $m$ 求和，得 $\displaystyle S_{\rm even}=\sum_{k=1}^m(2m-2k+1)=\sum_{k=1}^m[2(m-k)+1]$。
令 $j=m-k$，当 $k$ 从 $1$ 到 $m$ 时，$j$ 从 $m-1$ 到 $0$ ，$\displaystyle S_{\rm even}=\sum_{j=0}^{m-1}(2j+1)=2\cdot\frac{(m-1)m}2+m=m^2-m+m=m^2.$

3. 合并得到 $S$

$S=S_{\rm odd}+S_{\rm even}=\dfrac{m(m+1)}2+m^2=\dfrac{3m^2+m}2$，将 $m=\dfrac n2$ 代回得 $S=\dfrac{3(\frac n2)^2+\frac n2}2=\dfrac{\frac{3n^2}4+\frac n2}2=\dfrac{3n^2+2n}8=\dfrac{n(3n+2)}8.$

---

最终结果

综上，得

$$S=\begin{cases}\dfrac{3(n^2-1)}{8},&n为奇数,\\[10pt]\dfrac{n(3n+2)}8,&n为偶数.\end{cases}$$

这就是程序里的 n & 1 ? (n * n - 1) * 3 >> 3 : n * (n * 3 + 2) >> 3。