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