[LC周赛赛后发布会]WeeklyContest358

我不管！你歧视Java!我不管！我不管！我也是O(nlogn) + O(所有数字分解质因数），凭什么不让我过！呜呜呜呜呜呜！

看到上图应该懂了，本周周赛LZ真的看到了全过的希望：前三题20分钟bugfree就过了，第四题也算soft hard吧，LZ想了大概10分钟就有思路了，但是写得确实比较长。然后就是图上的悲剧了。LZ最后20分钟都在调参，试图把全体质数的范围降下来（sieve要的）。搞到最后差4个case。55555555


最后结果还是不错的，速三题，也算1000名了，可以接受，看看过几天出分能不能上2000。


另外LZ这周emo了，可能另外开个帖子说下。

你的O(所有数字分解质因数)估计有问题

aodeyyoyo 发表于 2023-8-13 00:56
你的O(所有数字分解质因数)估计有问题

所有数字质因数分解是肯定要做的
大概就是
for (int prime : allPrimes) {
   if (num % prime == 0) {
       curPrime++;
       while (num % prime ==0) {
                   num /= prime;
       }
    }

    if (num == 1) {
     break;

}

}

ATHOSD 发表于 2023-8-13 11:44
numi范围1e5其实可以在线性筛的同时把每个数的质数分数一起筛出来吧，暴力枚举的话质数密度还是蛮大的（大 ...

我没看懂你的代码，但是我回过头去看这个idea发现是对的。这样就不用每个num再单独分解了。

楼主这么有意思的？

盲猜lz每个case都筛质数了？
lc这种所有testcase一起计时的确实sb

南燕北巢 发表于 2023-8-13 06:46
盲猜lz每个case都筛质数了？
lc这种所有testcase一起计时的确实sb

懂了，那是把质数一边计算完然后静态的列在那里？

irgebtdd 发表于 2023-08-13 09:50:23
所有数字质因数分解是肯定要做的
大概就是
for (int prime : allPrimes) {

要用的是类似埃氏筛法的思想，接近O(max(nums))的时间复杂度就能做，你这个太暴力

aodeyyoyo 发表于 2023-8-13 10:07
要用的是类似埃氏筛法的思想，接近O(max(nums))的时间复杂度就能做，你这个太暴力

我用了，我这个是把每一个num break down

irgebtdd 发表于 2023-08-13 09:42:13
懂了，那是把质数一边计算完然后静态的列在那里？

是的，数据范围是固定的，所有case只筛一遍就行了

irgebtdd 发表于 2023-08-13 09:50:23
所有数字质因数分解是肯定要做的
大概就是
for (int prime : allPrimes) {

还可以更快
筛质数的时候可以顺手记录一下每个数的smallest prime factor，然后算score一直除spf就行了