[LC周赛赛后发布会]WeeklyContest358

南燕北巢 发表于 2023-8-13 10:18
还可以更快
筛质数的时候可以顺手记录一下每个数的smallest prime factor，然后算score一直除spf就行了

伪代码来一个？老实说我这个不慢的

是的这次第四题比较简单，虽然我也没筛出来质数，但是后面单调栈倒是比较清楚，看到了通过的希望。。。

zyrnj 发表于 2023-8-13 11:10
是的这次第四题比较简单，虽然我也没筛出来质数，但是后面单调栈倒是比较清楚，看到了通过的希望。。。

啥叫“没筛出来质数”？

numi范围1e5其实可以在线性筛的同时把每个数的质数分数一起筛出来吧，暴力枚举的话质数密度还是蛮大的（大概十个连续的数里面有一个质数），极端数据还是很容易T的

筛出来之后从大到小枚举最大质数分数（最大不会超过6），就可以O（n）计算最大质数分数为x的子数组数量了吧，瓶颈复杂度在这里，基本就是O（nlogn）

ATHOSD 发表于 2023-8-13 11:49
筛出来之后从大到小枚举最大质数分数（最大不会超过6），就可以O（n）计算最大质数分数为x的子数组数量了吧 ...

没懂，伪代码有吗？

irgebtdd 发表于 2023-08-13 12:01:23
没懂，伪代码有吗？

S=1e5
p[]存放所有质数
mark[i]表示i是否是质数
f[i]表示i的质数分数
虽然是两层循环，但每个数只会被最小质因子筛到，因此时间复杂度O(S)，说的比较简略，可以网上查一下质数线性筛
for(int i=2;i<=S;i++)
{
        if(!mark[i])
        {
                p[++tot]=i;
                f[i]=1;
        }
        for(int j=1;j<=tot;j++)
        {
                if(i*p[j]>S) break;
                mark[i*p[j]]=1;
                if(i%p[j]==0)
                {
                        f[i*p[j]]=f[i];
                        break;
                }
                else
                {
                        f[i*p[j]]=f[i]+1;
                }
        }
}

ATHOSD 发表于 2023-8-13 21:07
S=1e5
p[]存放所有质数
mark表示i是否是质数

tot什么鬼？是初始为0吗？

irgebtdd 发表于 2023-08-13 21:42:35
tot什么鬼？是初始为0吗？

对呀，就是个质数计数器

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

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