2018 ICPC北京站C题-Pythagorean triple

未分类

---

原题链接：https://hihocoder.com/problemset/problem/1872

下文用到的数学符号：
$(a,b)$表示$a,b$的最大公约数。
$[a,b]$表示$a,b$的最小公倍数。
$[x]$表示如果$x$为真返回$1$，否则返回$0$。
$a \nmid b$表示$a$不能整除$b$。

题意：
问满足

$$a^2 + b^2 = c^2,1 \leq a<b<c \leq n$$
的三元组$(a,b,c)$有多少个。

解析：
要求的就是斜边小于等于$n$的商高三角形的个数。
首先本源商高三角形的结论是：

$$a=r^2-s^2,b=2rs,c=r^2+s^2$$
其中$r>s \geq 1,(r,s)=1,2 \nmid (r+s)$。

在给定$n$的情况下，一个本源商高三角形通过边乘同一个正整数可以拓展出$n/(r^2+s^2)$个商高三角形，所以也就是求：

$$\begin{align*} ans = \sum_{r^2+s^2 \leq n,r>s\geq 1,(r,s)=1,2 \nmid (r+s)} \lfloor \frac{n}{r^2+s^2} \rfloor \end{align*}$$

设

$$f(n)=\sum_{r^2+s^2\leq n,min(r,s) \geq 1,(r,s)=1} \lfloor \frac{n}{r^2+s^2} \rfloor$$
$$g(n) = \sum_{r^2+s^2\leq n,min(r,s)\geq 1,(r,s)=1,2 \nmid [r,s]} \lfloor \frac{n}{r^2+s^2} \rfloor$$

可知$ans=\frac{f(n)-g(n)}{2}$。

先求$f(n)$：
设

$$\begin{align*} f'(n)&=\sum_{r^2+s^2\leq n,min(r,s) \geq 1} \lfloor \frac{n}{r^2+s^2} \rfloor\\ &= \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \sum_{min(r,s) \geq 1}[i==r^2+s^2] \end{align*}$$
那么$f(n)=\sum_{k=1}^{\sqrt n} f'(\frac{n}{k^2})\mu(k)$
记录$h(m)=\sum_{i=1}^m \lfloor \sqrt{m-i*i} \rfloor$，$m$是$\lfloor \frac{n}{i} \rfloor$，只有$\sqrt{n}$个这样的$m$。$f'(n)$可以用数论分块求解，$\sum_{min(r,s) \geq 1}[i==r^2+s^2]$这部分可以通过二分，使用预处理好的$h$差分计算。

再考虑求$g(n)$：
同样的，设

$$\begin{align*} g'(n) &= \sum_{r^2+s^2\leq n,min(r,s)\geq 1,2 \nmid [r,s]} \lfloor \frac{n}{r^2+s^2} \rfloor \\ &= \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \sum_{min(r,s)\geq 1,2 \nmid [r,s]}{[i==r^2+s^2}] \end{align*}$$
那么$g(n)=\sum_{k=1}^{\sqrt{n}} g'(\frac{n}{k^2})\mu(k)[2 \nmid k]$
可以用类似求解$f'(n)$的方法来求解$g'(n)$。

求解$f'(n),g'(n)$的时间复杂度是$O(\sqrt{n}logn)$的，求解$f(n),g(n)$的时间复杂度是：

$$\sum_{k=1}^{\sqrt{n}} O(\sqrt{\frac{n}{k^2}}logn) = O(\sqrt{n}log^2n)$$

预处理$h$的时间复杂度我不会算...不过在$n=10^9$时进行计算也可以很快得出结果。

参考程序：https://paste.ubuntu.com/p/hmJmgFMV39/