某大厂二面挂,算法没手撕出来

输入很多数字,每个数字一行,输出每个数字有多少总分解的数量。

a=a1*a2*a3... (ai<=a(i+1)) 同时要求1<ai

例如:10 = 1x10 10 = 2x5。所以输出2。这个例子我可能记错了

有算法佬么,此题什么思路呢,我使用暴力搜索会超时

全部评论
预处理2到max(输入数字x)这些数的最小质因子是什么。然后logx级别的时间复杂度进行质因数分解。比如一个数是2的a次方*3的b次方*5的c方。那他的总分解数就是(a+1)*(b+1)*(c+1)/2。
2 回复 分享
发布于 2024-10-22 09:45 广东
质因数分解
点赞 回复 分享
发布于 2024-10-31 14:48 上海
有个问题,1*2*5不算吗
点赞 回复 分享
发布于 2024-10-22 09:33 黑龙江
优化根号n,再加记忆应该可以吧
点赞 回复 分享
发布于 2024-10-22 09:30 浙江
如果每个数都不会很大,比如1e9这种,可以预处理,用dp统计每个数的因子数,答案是因子数/2,上取整
点赞 回复 分享
发布于 2024-10-22 09:23 广东
请问有leetcode有类似题目么,没找到相似的
点赞 回复 分享
发布于 2024-10-21 21:52 北京
感觉应该是dp
点赞 回复 分享
发布于 2024-10-21 21:45 天津
dp 吧
点赞 回复 分享
发布于 2024-10-21 21:45 山东

相关推荐

2025-12-22 16:31
已编辑
桂林电子科技大学 Python
很奥的前端仔:如果你接了offer 临时又说不去 hr确实要多做一些工作。 当然如果是接offer之前当我没说
点赞 评论 收藏
分享
2025-12-28 16:32
重庆邮电大学 Java
程序员花海:1.技能放最后,来面试默认你都会,技能没啥用 2.实习写的看起来没啥含金量,多读读部门文档,包装下 接LLM这个没含金量 也不要用重构这种 不会给实习生做的 3.抽奖这个还是Demo项目,实际在公司里面要考虑策略,满减,触发点,触发规则 库存 之类的,不是这个项目这么简单 4.教育背景提前,格式为 教育背景 实习 项目 技能 自我评价
简历被挂麻了,求建议
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务