Splendor White's blog

标签 · gcd

首页

关于

归档

算法数据结构题解数论gcd唯一分解定理

P5150 生日礼物 题解

虽然题目不难,但背后蕴含的考点还是很有意思的。 本题的核心考点是唯一分解定理。 此考点曾在NOIP中涉及,非常重要!!! 例如 NOIP2009 Hankson的趣味题 唯一分解定理:设 pip_ipi​ 表示第 iii 个质数,那么对于任意正整数NNN,都有唯一的一组 a1,a2,a3…ana_1,a_2,a_3\dots a_na1​,a2​,a3​…an​ ,使得 N=p1a1×p2a2×p3a3×⋯×pnanN=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times\dots\times p_n^{a_n} N=p1a1​​×p2a2​​×p3a3​​×⋯×pnan​​ 其中 aia_iai​ 可以等于000。 用白话文说:任何数都可以表示为他的质因数们的若..

更多
算法数据结构题解数论gcd

P8458 「REOI-p1」打捞 题解

如果将所有数列都扩展到 kkk 的长度, 1e91e91e9 级别的数组肯定会时间空间双爆炸。 所以这个题要利用周期性。 不难发现,两个数列的最小正周期为 lcm(li,lj){\rm lcm}(l_i,l_j)lcm(li​,lj​) , 我们真正需要处理的是在这个最小正周期内的交叉积。 尽管如此,若 li,ljl_i,l_jli​,lj​ 都是质数,他们的最小正周期也可以很长很长。遍历最小正周期求交叉积依然无法AC。 通过分析那 60%60\%60% 的数据我们可以发现,若 li,ljl_i,ljli​,lj 互质,那么,在一个最小正周期中, aia_iai​ 中的每一个元素,都把 aja_jaj​ 中的每一个元素乘了 111 次,而且只乘了 111 次。那么我们可以利用分配律,得 ∑aiaj=∑(ai..

更多