Loading...

SPOJ20173 Counting Divisors

check评论:0 条 remove_red_eye浏览量:399 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-10

莫比乌斯反演题目

题目大意:给出$n$求$ \sum _{i=1} ^n σ_0(i^2) $

其中$σ_0$是除数函数,$0$代表$0$次方

我们需要想个方法把平方去掉

设$n=\prod_{i=1}^k p_i^{a_i}$,$n^2=\prod_{i=1}^k p_i^{2a_i}$

$σ_0(n)=\prod_{i=1}^k (a_i+1)$

$σ_0(n^2)=\prod_{i=1}^k (2a_i+1)$

$σ_0(n^2)=\sum_{s \subseteq \left\{1,2,...,k\right\} } 2^{\left|S\right|} \times \prod_{i \in S}a_i $

$σ_0(n^2)=\sum_{d|n}\mu^2(d)$

整理一下式子:

设$f(n)=\sigma(n^2)$,$g(n)=2^{\omega(n)}$,$h(n)=\mu^2(n)$

$f=g*1\quad\quad g=h*1$

$f=(h*1)*1=h*(1*1)=h*\sigma_0$

所以:

$\sum_{i=1}^nf(i)=\sum_{i=1}^n(h*\sigma_0)(i)=\sum_{ij \leq n}h(i)\sigma_0(j)=\sum_{i=1}^n \mu^2(i) \sum_{j=1}^{\left[\frac{n}{i}\right]} \sigma_0(j)$

显然需要预处理$\mu^2(n)$和$\sigma_0(n)$的前缀和

利用杜教筛的复杂度分析可知,若线性预处理出前$n^{2/3}$项的前缀和,此时复杂度达到最优$O(n^{2/3})$,利用积性预处理。

约束个数前缀和显然很好计算:

$\sum_{i=1}^n\sigma_0(i)=\sum_{i=1}^n\left[\frac{n}{i}\right]$,用$O(\sqrt n)$分段计算即可

至于$\mu^2(n)$的前缀和,从“n以内无平方因子的数的个数”这个意义出发,考虑容斥,不难得出:

$\sum_{i=1}^n\mu^2(i)=\sum_{i=1}^{\sqrt n}\mu(i)\left[\frac{n}{i^2}\right]$

$O(\sqrt n)$暴力计算即可

可分析得,总复杂度为$O(n^{2/3})$

code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,sig[100000005],N,a[200005];
int p[10000005];
bool mark[100000005];
char mul[100000005];
int smu[100000005],L;
void Init(int n)
{
    sig[1]=1;
    smu[1]=1;
    mul[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!mark[i])
        {
            p[++p[0]]=i;
            mul[i]=-1;
            smu[i]=1;
            sig[i]=2;
        }
        for(int j=1;j<=p[0]&&p[j]*i<=n;j++)
        {
            mark[p[j]*i]=1;
            if(i%p[j]==0)
            {
                sig[p[j]*i]=sig[i]/(smu[i]+1)*(smu[i]+2);
                smu[p[j]*i]=smu[i]+1;
                mul[p[j]*i]=0;
                break;
            }
            sig[p[j]*i]=sig[i]*2;
            smu[p[j]*i]=1;
            mul[p[j]*i]=-mul[i];
        }
    }
    for(int i=1;i<=n;i++) 
    {
        sig[i]+=sig[i-1];
        smu[i]=smu[i-1]+abs((int)mul[i]);
    }
}

ll R(ll x)
{
    if(x<=L) 
    {
        return sig[x];
    }
    ll res=0;
    for(ll i=1,j;i<=x;i=j+1)
    {
        j=(x/(x/i));
        res+=(j-i+1)*(x/i);
    }
    return res;
}
ll Smu(ll x)
{
    if(x<=L) 
    {
        return smu[x];
    }
    ll res=0;
    for(ll i=1;i*i<=x;i++)
    {
        if(mul[i]) 
        {
            res+=mul[i]*(x/(i*i));
        }
    }
    return res; 
}
void solve(ll n)
{
    int m=sqrt(n);
    ll ans=0;
    ll pre=smu[m],tt;
    for(int i=1;i<=m;i++) 
    {
        if(mul[i]) 
        {
            ans+=R(n/i);
        }
    }
    for(ll i=m+1,j;i<=n;i=j+1)
    {
        j=(n/(n/i));
        tt=Smu(j);
        ans+=(tt-pre)*(R(n/i));
        pre=tt;
    }
    printf("%lld\n",ans);
}
int main()
{
    cin>>T;
    ll mx=0;
    N=1000000000000;
    for(int i=1;i<=T;i++) 
    {
        scanf("%lld",&a[i]);
        mx=max(mx,a[i]);
    }
    if(mx<=10000) 
    {
        L=10000;
    }
    else 
    {
        L=pow(N,2.0/3.0);
    }
    Init(L);
    for(int i=1;i<=T;i++)
    {
        solve(a[i]);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名