[HDU-6834] Yukikaze and Smooth numbers

Posted on Edited on In

[HDU-6834] Yukikaze and Smooth numbers

题意：计算 \([1,n]\) 中只包含 \([1,k]\) 的质因数的数个数

让人联想到Min25筛的 \(dp\) 模型

设 \(m=\sqrt n\) ，可以对于 \(k > m\) 和 \(k\leq m\) 讨论

Case1: \(k\leq m\)

此时可以直接套用类似Min25筛的 \(dp\) 模型求解

令 \(dp_{i,j}\) 为 \([1,j]\) 只包含 \([1,i]\) 的质因数的数个数

则 \(dp_{i,j}=\sum_k dp_{i-1,\lfloor \frac{j}{prime_i^k}\rfloor }\)

要求的是 \(dp_{k,n}\) ，第二维状态是 \(O(m)\) 级别的

直接写当然是近似于 \(O(m\cdot \pi(n))=O(\frac{n}{\log n})\) 级别的

加上Min25筛的优化，令 \(dp_i,j\) 不包含单质数和1的情况，以减少转移情况

如果从大到小考虑每个质数，那么只需要考虑 \(j\ge prime_i^2\) 的第二维状态，以减少很多的 \(dp\) 时间

沿用Min25筛复杂度证明，是 \(O(\frac{n^{\frac{3}{4}}}{\log n})\) 的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define id(x) (x<=m?x:cnt-n/x+1)

int dp[N],g[N],st[N],cnt;

if(k==1){ puts("1"); continue; }
m=sqrt(n),cnt=0;
rep(i,1,n) st[++cnt]=i=n/(n/i),dp[cnt]=0; // 不包括质数本身和1
int sz=1;
while(pri[sz+1]<=k) sz++;
int p=0;
rep(i,1,cnt){
    while(p<sz && pri[p+1]<=st[i]) p++;
    g[i]=p;
}    
rep(i,1,cnt) for(ll x=pri[sz]*pri[sz];x<=st[i];x*=pri[sz]) dp[i]++;
for(reg int i=sz-1;i;--i) {
    for(reg int j=cnt,tmp=pri[i]*pri[i];st[j]>=tmp;--j) {
        reg int x=st[j];
        while(x>=tmp) {
            x/=pri[i];
            dp[j]+=dp[id(x)]+g[id(x)]-i+1;
        }
    }
}
printf("%d\n",dp[cnt]+sz+1);

\[\ \]

Case2 : \(k> m\)

可以把问题转化为求不合法部分，即 \(\sum_{prime_i>k}\lfloor \frac{n}{prime_i}\rfloor\)

采用数论分段计算 \(\lfloor \frac{n}{i}\rfloor\) ，那么剩下的问题就是要求一段区间内的质数个数

同样采用类似上面的模型，

令 \(dp_{i,j}\) 为 \([1,j]\) 内与前 \([1,i]\) 内质数互质的个数以及这些质数本身，不包括1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n,m;
int dp[N],g[N],st[N],cnt;
#define id(x) (x<=m?x:cnt-n/x+1)

int Count(int n) {
    if(n<N) return pcount[n];
    ::n=n,m=sqrt(n),cnt=0;
    rep(i,1,n) st[++cnt]=i=n/(n/i),dp[cnt]=i-1;
    for(reg int i=1;pri[i]<=m;++i) {
        for(reg int j=cnt,tmp=pri[i]*pri[i];st[j]>=tmp;--j) {
            reg int k=st[j]/pri[i];
            dp[j]-=dp[id(k)]-(i-1);
        }
    }
    return dp[cnt];
}

具体复杂度没有算过，应该不会太高