HDU 6134 Battlestation Operational

题目大意：求$f(n)=\sum_{i=1}^n\sum_{j=1}^i \lceil \frac{i}{j} \rceil [(i,j)=1]$ 。

莫比乌斯反演

首先，有一个据说很著名的等式：
$$
\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor =\sum_{i=1}^n \sigma(i)
$$
其中$\sigma(n)$ 为$n$ 的因数个数。这个等式可以由筛法证明（见代码）。

然后我们来化简下题目中所要求的函数$f(n)$ 。
$$
f(n)=\sum_{i=1}^n \sum_{j=1}^i \lceil \frac{i}{j} \rceil [(i,j)=1]\\
=\sum_{i=1}^n(\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1] +\varphi(i)-1)\\
=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1] +\sum_{i=1}^n\varphi(i)-n\\
$$
设$g(n)=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1],i=k_1d,j=k_2d$ ，则有
$$
g(n)=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1]\\
=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor \sum_{d|(i,j)}u(d)\\
=\sum_{d=1}^nu(d)\sum_{k_1=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{k_2=1}^{k_1}\lfloor \frac{k_1}{k_2} \rfloor\\
=\sum_{d=1}^nu(d)\sum_{k_1=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{k_2=1}^{k_1}\sigma(k_2)
$$
$h(n)=\sum_{i=1}^n\sum_{j=1}^{i}\sigma(j)$ 预处理的复杂度为$O(nlogn)$ 。

于是$f(n)=\sum_{d=1}^nu(d)h(\lfloor \frac{n}{d} \rfloor)+\sum_{i=1}^n\varphi(i)-n$ 可以在$O(\sqrt{n})$ 的复杂度求出。

代码如下：

#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1000001;
const ll p=1e9+7;
ll d[N],h[N],sumd,n;
ll prime[N],vis[N]={1,1},k,phi[N]={0,1},pphi[N],mu[N]={0,1},pmu[N];
ll Max(ll a,ll b){
    return a>b?a:b;
}
void init(){
    for(int i=2;i<N;++i){
        if(!vis[i]){
            prime[k++]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=0;j<k&&prime[j]*i<N;++j){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else{
                mu[i*prime[j]]=-mu[i];
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
    for(int i=1;i<N;++i)
        for(int j=i;j<N;j+=i)
            d[j]++;//预处理\sigma(n)
    for(int i=1;i<N;++i){
        sumd=(sumd+d[i])%p;
        h[i]=(h[i-1]+sumd)%p;
    }
    for(int i=1;i<N;++i){
        pphi[i]=(pphi[i-1]+phi[i])%p;
        pmu[i]=pmu[i-1]+mu[i];
    }
}
ll solve(ll n){
    ll ans=((pphi[n]-n)%p+p)%p;
    for(ll d=1;d<=n;){
        ll pd=Max(d,n/(n/d));
        ans+=(pmu[pd]-pmu[d-1])*h[n/d]%p;
        ans=(ans+p)%p;
        d=pd+1;
    }
    return ans;
}
int main(void){
    init();
    while(~scanf("%I64d",&n))
        printf("%I64d\n",solve(n));
}