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。 用白话文说：任何数都可以表示为他的质因数们的若..
更多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..
更多