[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})\)的
#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
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];
}
具体复杂度没有算过,应该不会太高