首页 > 代码库 > UVA 10780
UVA 10780
UVA 10780
Problem
给两个整数M，N，要求找到最小的正整数K，使得（M^k）可整除（N ! ）。输出K，若不存在，输出不存在。
Limits
Time Limit(ms): 3000
Memory Limit(MB): No Limit
M: [2, 5000]
N: [1, 10000]
不超过500个case
Solution
分解素因数，将M表示成(Pi1^Ki1)*(Pi2^Ki2)*......*(Pin^Kin) ，再将 N ! 表示成 (Pj1^Kj1)*(Pj2^Kj2)*......*(Pjn^Kjn) 。其中P表示素数，K表示幂。枚举M的每一个素数P，设该素数的幂为K1，找到 N ! 分解形式中素数P的幂K2（若不存在则K2=0），那么answer=（K2／K1）min.（answer=0表示答案不存在）
More
需要打表。表一存储[1, 10000]中每个数的分解素因数形式，表二存储[1, 10000]中每个数的阶乘的分解素因数形式。
表一用素数打表、通过素数表分解素因数的方法即可求。但注意，最好用两个vector，一个存储(Pi1^Ki1)*(Pi2^Ki2)*......*(Pin^Kin）里的P（需保证单调递增），一个存储K，两个vector长度一样，并会发现长度不超过4或5。这里用了一个性质，10^9内每个数的所有素因数的种类数很小。
表二需要用到有序表合并，即将两个单调递增的表合并成一个单调递增的表，这个过程与“归并排序”的合并步骤是类似的。同样用两个vector存储，长度不会超过1230多。又用到一个性质，[1,10000]中只有1230多个素数。
有了两个表就可以处理Solution中的问题了。处理方法多样，可以先存储记录后O(1)查找K2，也可以用two-pointers的方法查找K2。
Complexity
Time Complexity: O(t*N)（均摊情况下t不大，极端情况为10^3级别）
Memory Complexity: O(1000*N)
Source
UVA 10780
Code
UVA 10780 From My Github
UVA 10780
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。