menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[莫比乌斯函数+线性筛]BZOJ3309【DZY Loves Math】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

令 $f(x)$ 表示 $x$ 质因数分解之后最大的次幂,$m$ 次询问,每次求 $\sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j)]$ 。

解题报告

先正常操作一下:

$$ \sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j)]=\sum_{T=1}^{min\{A,B\}}\lfloor{A\over T}\rfloor\lfloor{B\over T}\rfloor\sum_{k|T}f(k)\mu({T\over k}) $$


上面是谁都会环节,我用调和级数算 $H(T)=\sum_{k|T}f(k)\mu({T\over k})$ 然后果断GG,想线性筛发现这并不是积性函数,就搞不来了……于是膜PoPoQQQ

大概就是说考虑 $\mu({T\over k})$ ,会发现 $k$ 的每一个素数都不能和 $T$ 相差 $>1$ ,否则就没有贡献了。

因此决定 $f(k)$ 的是 $T$ 中次幂最大的那些素数,此时有两种情况:

  1. 所有素数的次幂不都相等

    • 此时决定 $\mu({T\over k})$ 的是次幂不是最大的素数的选取情况(每个素数只有两种情况:相同和 $-1$ ),显然选取的奇偶情况相同(一个奇数的状态反一下变成偶数),所以这种情况没有贡献。
  2. 所有素数的次幂相等

    • 此时次幂最大的素数的选取情况同时决定了 $f(k)$ 和 $\mu({T\over k})$ ,只有一种特殊情况:$k$ 的每个素数都比 $T$ 少选一个,此时 $f(k)$ 为 $T$ 中最大次幂 $MAX-1$ ,反过来时 $\mu$ 变号,但是 $f$ 不是 $MAX-1$ 而是 $MAX$ ,所以有 $-1\mu({T\over k})$ 的贡献,其他情况则同第一种情况互相抵消。

因此可以用线性筛来处理出 $H(T)$ ,只需要讨论 $T$ 的所有素数的次幂是否相同即可。为了实现这个,需要记录 $num_i$ 表示 $i$ 的最小素数 $p_i$ 的次幂以及 $pw_i=p_i^{num_i}$ 。从而获得 $i$ 去除最小素数后的数来讨论。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=10000000;

int te,n,m,p[maxn+5],D[maxn+5],pw[maxn+5],num[maxn+5],H[maxn+5];bool pri[maxn+5];LL ans;

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