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