把十亿个数中的每个数都质因数分解？
by Ender_NaCl @ 2021-08-04 19:02:33
@[璀翼](/user/488775) 您真的确定 1e9 的数据用 10 个质因数就能分解？
by YukiChyan @ 2021-08-04 19:07:03
把十亿个数中的每个数都质因数分解？
就算最优$sqrt(1e9)$=5e4,你开得开5e4个(当然这可以实现)
把十亿个数中的每个数都质因数分解肯定$TLE$
by _l_l_l_l_l_ @ 2021-08-04 19:30:13
由于要让质因数尽可能的小，所以应该只需要前10个就能构造出来吧
by Cuiyi_SAI @ 2021-08-04 20:38:44
@[Ender_lhn](/user/245959) @[YukiChyan](/user/499997) @[WenZKbb](/user/522828) 不是每一个数都分解，而是用记录好的素数反推，用质数“构造”出一个可能合法的反素数，虽然我无法证明我的思路的正确性，但通过质因数构造出反素数我觉得可行，毕竟反素数的质因数分解后，它的质因数都是尽量小的,尽量多的，这样才能使因数个数更大，如：一对为2、3、3的质因数构造成的数的因子个数是肯定大于由97、97构造出来的数的因子个数的。
因此，我们要让质因数尽可能的小，这样才能更优的尝试构造出反素数。
by Cuiyi_SAI @ 2021-08-04 20:40:46
既然你想到了那么多，为什么不去写呢？你不写谁知道对不对
by Ender_NaCl @ 2021-08-05 08:46:51
我个人感觉你的思路有些问题（~~仅个人意见~~，但还是建议你写一下）题解里基本都是打表的，也有正解但很复杂，而且好像和组合没什么关系吧……
by Ender_NaCl @ 2021-08-05 08:51:36
@[Ender_lhn](/user/245959) 好吧，谢谢你的支持，我的老师说可以组合的，但好像有点复杂，尝试一下吧，并不提倡（毕竟想都不太明白，都不知道会敲出什么玩意了）
by Cuiyi_SAI @ 2021-08-05 10:41:59
@[Ender_lhn](/user/245959)
我用构造法写,过了，刚想写篇题解，发现发不出去了QWQ，特意到题解区转了转，才发现有位DALAO早就写出了构造法的正解，才30多行，dfs思想，比我那暴力枚举60多行强多了 QWQ
by Cuiyi_SAI @ 2021-08-06 13:43:24
@[璀翼](/user/488775) 好的，~~（看，我让你写写没错吧）~~
by Ender_NaCl @ 2021-08-06 17:28:51