20220416网易算法岗笔试第四题

题意

从数组中找出两个数,使得其乘积是一个仅由6个因子的数。这两个数可以相同,但是两个数的位置不能相同。
数组范围是 length < 200000

示例

4
2 6 3 9

示例解释

可以组成
2*6 = 12 [12的因子有6个,分别是1,2,3,4,6,12]
6*3 = 18 [18的因子有6个,分别是1,2,3,6,9,18]
2*9 = 18
这三对数组成的乘积均只有6个因子。

------------------------------------------------------------------
鶸求问大佬,这题该怎么做啊?😪😪

#实习##笔试题目#
全部评论
一个数的因子个数是6,那么它的质因数分解后的结果只有两种情况:p0^5,或者p0^2 *p1。所以需要对所有数进行质因数分解,讲这两种情况分开讨论;对每种情况,把因子分配到两个数中的一个即可。我的做法是筛出1e6的素数,然后balabala分开讨论,时间复杂度可以达到nlogn
1
送花
回复
分享
发布于 2022-04-20 19:17
蹲一个结果
点赞
送花
回复
分享
发布于 2022-04-17 08:36
秋招专场
校招火热招聘中
官网直投
大佬第三题a了没
点赞
送花
回复
分享
发布于 2022-04-17 10:24
我有个思路也不知道是否正确,6个因子的话,除了1和自己本身外的4个因子需要是3个素数的乘积,且这三个素数里有两个素数应该是相同的。(不知道我到这的思路有没有问题)。 代码:先素筛法求出200010里所有的素数,然后遍历输入数组(排序后的),如果是素数,记录出现次数,如果是合数,看能否分解成两个素数,对于这个合数的方案数等于分解得到两个素数出现的次数和(如果分解到的两个素数相等,需要特殊处理)。 总的复杂度是 nloglogn + n^3/2.
点赞
送花
回复
分享
发布于 2022-04-17 16:07

相关推荐

2 3 评论
分享
牛客网
牛客企业服务