Project Euler 513~522 (70%)

__Shi posted @ Thu, 20 Aug 2015 09:35:05 +0800 in PE with tags Project_Euler , 368 readers

513. Integral median.

中线定理(阿波罗尼斯定理)$\triangle ABC$的中线为$CI$,则:

[tex]CA^2+CB^2=\frac{AB^2}{2}+2CI^2[/tex]

具体做法尚不明确。

514. Geoboard Shapes.

根据期望的线性性,把面积公式里的每一部分分开来,算该部分出现的概率相加即可。

516. 5-smooth totients.

首先可以把范围内5-smooth的数预处理处理,数量大概为几千。      

一个满足条件的数,若包含除$2,3,5$以外的质因数,则该质因数最多只出现一次。

直接dfs找到这些数即可。

517. A real recursion.

把$-1$和$-a$看做两维,涉及到的位置呈阶梯状。对于一个高为$h$,距原点$w-1$的部分,对答案的贡献为:

[tex]{{w+h-2}\choose{n-1}}[/tex]

518. Prime triples and geometric sequences

枚举$b+1$,将$b+1$分解质因数后dfs枚举$(b+1)^2$的约数作为$a+1$,相加即可。

519. Tricolored Coin Fountains.

按列考虑。

$dp_{cnt, h}$表示现在已经用了$cnt$枚硬币,当前列的高度为$h$时的方案数。转移$O(1)$。

520. Simbers.

$dp_{digit, c1, c2, p1, p2}$表示当前已有$digit$位,有$c1$种数字出现且满足条件,$c2$种数字出现但不满足条件,$p1$个奇数未出现,$p2$个偶数未出现。

矩阵即可。

521. Smallest prime factor.

暴力做法:分段筛素数。

低于线性的做法:

令$C_p(n)$表示不超过$n$的最小质因子为$p$个数。

令$f_{n,k}$表示不超过$n$的数中,最小质因子大于$k$或为素数的数个数。

则$C_{prime_i}(n)=f_{n/prime_i,i}-f_{prime_i-1,i}$.

[tex]f_{n,k}=f_{n,k-1}-(f_{n/prime_{k-1},k-1}-f_{prime_{k-1}-1,k-1})[/tex]

不超过$n$的素数和也可用类似的方法求得。

复杂度据说为$O(n^{3/4})$.

blog comments powered by Disqus