【UOJ188】 Sanrd【类min_25筛】,uusee电视

文件名：【UOJ188】 Sanrd【类min_25筛】,uusee电视 【UOJ188】 Sanrd【类min_25筛】

题意：设$f(i)$表示$i$的不严格次大质因子（没有为$0$），求${\sum }_{i=l}^{r}f(i)$

$l\le r\le 10^{11}$

这种和质因数有关的奇奇怪怪的函数的前缀和可以试试魔改min_25筛

设

$$S(n,j)=\sum _{i=2}^n[minp(i)>p_j]f(i)$$

枚举最小的质因子$p_k$以及次数$e$

如果$p_k$不是次大质因子，直接递归到$S(\lfloor \frac{n}{p_k^e}\rfloor ,k)$

否则考虑$p_k$的贡献

如果是严格次大，那么枚举最大的质因子

否则就是$[e>1]$

$$S(n,j)=\sum _{k=j+1}^{p_k\le \sqrt{n}}\sum _{e=1}^{p_k^e\le n}(S(\lfloor \frac{n}{p_k^e}\rfloor ,k)+\sum _{i=p_k+1}^{\lfloor \frac{n}{p_k^e}\rfloor }[i\in prime]+[e>1])$$

注意$p_k+1$可能大于$\lfloor \frac{n}{p_k^e}\rfloor$，要特判一下

然后用min_25的方法预处理出质数个数的前缀和即可

#include <iostream>#include <cstdio>#include <cstring>#include <cctype>#include <cmath>#define MAXN 1000005using namespace std;const int N=1e6;int np[MAXN],pl[MAXN],cnt;void init(){np[1]=1;for (int i=2;i<=N;i++){if (!np[i]) pl[++cnt]=i;for (int j=1,x;(x=i*pl[j])<=N;j++){np[x]=1;if (i%pl[j]==0) break;}}}typedef long long ll;ll val[MAXN],n,m;int key[MAXN],yek[MAXN],tot;inline int getkey(ll x){return x<=m? key[x]:yek[n/x];}ll g[MAXN];ll S(ll n,int j){if ((ll)pl[j]*pl[j]>n) return 0;ll sum=0;for (int k=j+1;(ll)pl[k]*pl[k]<=n&&k<=cnt;k++)for (ll e=1,v=pl[k];v<=n;e++,v*=pl[k])sum+=S(n/v,k)+pl[k]*(max(0ll,g[getkey(n/v)]-k)+(e>1));return sum;}ll solve(ll N){m=sqrt(n=N);tot=0;for (ll l=1,r;l<=n;l=r+1){r=n/(n/l);val[++tot]=n/l;if (val[tot]<=m) key[val[tot]]=tot;else yek[n/val[tot]]=tot;}for (int i=1;i<=tot;i++) g[i]=val[i]-1;for (int j=1;j<=cnt;j++)for (int i=1;(ll)pl[j]*pl[j]<=val[i];i++)g[i]-=g[getkey(val[i]/pl[j])]-j+1;return S(n,0);}int main(){init();ll l,r;cin>>l>>r;cout<<solve(r)-solve(l-1);return 0;}