【刷题记录】BZOJ2154 crash的数字表格莫比乌斯反演-白红宇

【刷题记录】BZOJ2154 crash的数字表格莫比乌斯反演

阅读量：5296 次

发布时间：2019-06-14

本文共 1588 字，大约阅读时间需要 5 分钟。

治好了我多年的公式恐惧症

（放洛谷题号的原因是BZOJ上很多内容是限制级的（雾））

题目大意:已知M，N，求 $ans =\sum_{i=1}^n\sum_{j=1}^m{\frac {ij} {(i,j)} }$

(我采用数论教材上的方法表示最大公因数，即（i,j)表示i，j的最大公约数）

那么，我们开始吧。

不妨设n<m

令 d = (i,j) ,有 $ans = \sum _{d=1}^{n} \sum_{\begin{matrix} (i,j)=d \\ 1\leqslant i\leqslant n, \\ 1\leqslant j \leqslant m, \end{matrix}}\frac {ij} d$

即 $ans = \sum _{d=1}^{n} d\sum_{(i,j)=1}^{1\leq i\leq [\frac nd],1\leq j\leq [\frac md]}{ij}$

接下来是莫比乌斯函数的性质: $\sum _{x|d} \mu (x) = 1$ 当且仅当d = 1

$ans = \sum _{d=1}^{n} d\sum_{i=1}^{[\frac nd]}\sum_{j=1}^{[\frac md]}\sum_{x|(i,j)}\mu (x){ij}$

转化为枚举x

$ans = \sum_{d=1}^{ n}d\sum_{x=1}^{[\frac nd]}\mu(x)x^2\sum_{j=1}^{[\frac n {dx}]}\sum_{i=1}^{[\frac m {dx}]}ij$

枚举t=dx

$ans = \sum_{t=1}^{ n}t\sum_{i=1}^{[\frac nt]}\sum_{j=1}^{[\frac mt]}ij\sum_{x|t}\mu(x)x=\sum_{t=1}^{ n}t(\sum_{i=1}^{[\frac nt]}i)(\sum_{j=1}^{[\frac mt]}j)\sum_{x|t}\mu(x)x$

中间两个和式为等差数列求和，可以O(1)得到结果

经过完全归纳法证明， $f(i)=\sum_{x|i}\mu(x)x$ 为积性函数

证明如下：

当i为质数时，显然 f(i)=1-i

记p为任意质数

当 (i,p)=1 时

有 $f(ip)=\sum_{x|ip}x\mu(x)=f(i)+\sum _{xp|ip}(xp)\mu(xp)=f(i)-pf(i)=f(p)*f(i)$

证完

接下来考虑线性筛的实现

考虑当 (i,p)=p

有 $f(ip)=\sum_{x|ip}x\mu(x)=f(i)+\sum _{xp|ip}(xp)\mu(xp)=f(i)-0=f(i)$

所以线性筛完成

依靠线性筛预处理后，可以O(n)时间预处理，再用O(n)时间得出结果

然而此题还可以再次优化

考虑到 $[\frac nt]$ 和 $[\frac mt]$ 可以数论分块

时间复杂度可以优化至O(n+sqrt(n))

这样可以解决多组数据的情况

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n,m;#define ll long long#define mod 20101009#define inv2 10050505#define N 10000000int prime[N+9],mu[N+9];bool notprime[N+8];ll sum(int x){    return (((((ll)x*(x+1))%mod)*inv2)%mod);}int main(){    scanf("%d%d",&n,&m);    if(n>m)swap(n,m);    notprime[1]=mu[1]=1;int tot = 0;    for(int i = 2; i <= n; i ++)    {        if(!notprime[i])        {            prime[++tot]=i;            mu[i]=(1-i+mod)%mod;        }        for(int j = 1; j <= tot &&prime[j]*i<=n; j ++)        {            notprime[prime[j]*i]=1;            if(i%prime[j]==0)            {                mu[i*prime[j]]=mu[i];                break;            }            else             {                mu[i*prime[j]]=(((ll)mu[i]*(1-prime[j])%mod)+mod)%mod;            }        }        mu[i]=((((ll)i*mu[i])%mod+mu[i-1])%mod+mod)%mod;    }    int ans = 0;    for(int i = 1,last; i <= n; i =last +1)    {        last = min(n/(n/i),m/(m/i));        ans = (((((sum(n/i)*sum(m/i))%mod)*(mu[last]-mu[i-1]))%mod+mod)%mod+ans)%mod;    }    printf("%d",ans);}

转载于:https://www.cnblogs.com/akonoh/p/10216755.html

你可能感兴趣的文章