琪露诺的完美算法课

本文主要是介绍琪露诺的完美算法课，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给出$a$的范围$[x,y]$，求满足$c^2⩽a^2+b^2⩽c^2+1$的边长均为正整数的三角形个数

Solution

对原式变形：
$$a^2=c^2-b^2=(c+b)(c-b)$$

$$a^2-1=c^2-b^2=(c+b)(c-b)$$

则若$a^2=i\ast j(i>j)$，且$i$与$j$奇偶性相同，有三角形$(a,\frac{i-j}{2},\frac{i+j}{2})$，$a^2-1$同理

此时，时间复杂度为$O(n^2)$，期望得分$30pts$

重新观察一下，我们可以发现

设$f_i$为$a=i$时的三角形数量，$d_i$为$i$的约数数量，$nu{m}_i$为$i$的最小质因数的出现次数，$p_i$为$i$最大的奇数约数

1 计算$f$

1.1

对于$a$为奇数的情况：
$$f_a=\frac{d_a}{2}\text{\hspace{1em}(1.1)}$$

proof:

约数两两配对

1.2

对于$a$为偶数的情况：
$$f_a=\frac{d_{p_a}\ast (nu{m}_a-1)}{2}(p_a\%2=1,p_a\ast 2^{nu{m}_a}=a)\text{\hspace{1em}(1.2)}$$

proof:

对于奇数$p_a$，有$d_{p_a}$种，将$nu{m}_i$个$2$分入两个数中，每个数至少有一个·，则为$(nu{m}_i-1)$

可以用线性筛预处理$d$

线性筛求约数个数

2 计算$f_{a^2}$

2.1

若$a$为奇数，
$$f_{a^2}=\frac{d_{a^2}}{2}\text{\hspace{1em}(2.1)}$$

对于每个$i$，设$d{f}_a=d_{a^2}=(2k_1+1)(2k_2+1)...(2k_n+1)$

可以在预处理$d$的时候一起处理

2.2

若$a$为偶数，
$$f_{a^2}=\frac{d_{p_a^2}\ast (2\ast nu{m}_i-1)}{2}\text{\hspace{1em}(2.2)}$$

3 计算$f_{a^2-1}$

3.1

若$a$为偶数，则$a^2-1$为奇数，所以
$$f_{a^2-1}=\frac{d_{a^2-1}}{2}=\frac{d_{a+1}\ast d_{a-1}}{2}\text{\hspace{1em}(3.1)}$$

3.2

若$a$为奇数，则$a^2-1$为偶数，所以
$$f_{a^2-1}=\frac{d_{p_{i+1}}\ast d_{p_{i-1}}\ast (nu{m}_{i+1}+nu{m}_{i-1}-1)}{2}\text{\hspace{1em}(3.2)}$$
最后枚举$a$，根据奇偶性作答即可

这篇关于琪露诺的完美算法课的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---