menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[Min_25筛]UOJ188(UR #13)【Sanrd】题解
apps UOJ
local_offer 查看标签
comment 0 条评论

题目概述

求 $\sum_{i=L}^{R}f(i)$ ,$f(n)$ 表示 $n$ 的次大质因子(相同质因子算多次),若次大质因子不存在则 $f(n)=0$ 。

解题报告

Min_25筛的膜法…… $f(n)$ 并不是个积性函数,但是我们发现可以通过枚举一个素数,然后分别计算这个素数乘上另一个素数或者一个合数的贡献,这可以对应到Min_25筛 $S(n,j)$ 的计算方法。

由于 $S(n,j)$ 上一个素数是 $p_{j-1}$ ,因此乘上素数的贡献是 $p_{j-1}[g_n-(j-1)]$ ,$g_n$ 是预处理出的素数个数。

如果乘上一个合数,那么显然 $p_{j-1}$ 将不会成为次大质因数,所以直接统计 $S(\lfloor{n\over p_i^k}\rfloor,i+1)+f(p_i^{k+1})$ 即可。

示例程序

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxs=632456;

int S;int p[maxs+5];bool pri[maxs+5];
int m,ID[2][maxs+5];LL L,R,n,a[maxs+5],g[maxs+5];

inline void Make(int n){
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            {pri[t]=true;if (!(i%p[j])) break;}
    }
}
#define ID(x) ((x)<=S?ID[0][x]:ID[1][n/(x)])
LL Sum(LL a,int b){
    if (a<=1||p[b]>a) return 0;int k=ID(a);LL ans=(b>1?(LL)p[b-1]*(g[k]-(b-1)):0);
    for (int i=b;i<=p[0]&&(LL)p[i]*p[i]<=a;i++){
        LL A=p[i],B=A*A;
        for (int j=1;B<=a;j++,A=B,B*=p[i])
            ans+=Sum(a/A,i+1)+p[i];
    }return ans;
}
inline LL Min25(LL x){
    n=x;S=sqrt(n);m=0;
    for (LL l=1,r;l<=n;l=r+1){
        r=n/(n/l);a[++m]=n/l;g[m]=a[m]-1;
        a[m]<=S?ID[0][a[m]]=m:ID[1][n/a[m]]=m;
    }
    for (int j=1;j<=p[0]&&p[j]<=S;j++)
        for (int i=1;i<=m&&(LL)p[j]*p[j]<=a[i];i++)
            g[i]+=j-1-g[ID(a[i]/p[j])];
    return Sum(n,1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%lld%lld",&L,&R);Make(maxs);printf("%lld\n",Min25(R)-Min25(L-1));return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up