HDU 6134

tiberius 2018-07-17 原文

题意略。

思路：

我们先不考虑[(i , j) == 1]，在此情况下，其实这个值是sum( [ (i , j) == 1,2,3,….,n ] ) 这些情况。我们要求的仅仅是其中的第一部分而已。也即：

F(1) = f(1) + f(2) + f(3) + …. + f(n)。[1,2,3,….,n 是1的整数倍]

在这里，我们令 g(i) 为 i / 1 + i / 2 + …. + i / i 向下取整之和。令 G(i) 为左式向上取整之和，我们有一个递推公式：

g(i) = G(i) – i + cnt[i] G(i) = g(i – 1) + i

其中cnt[i]记录的是 i 的因子个数。

我们要想求出在 n 条件下的 F(1)，则F(1) = G(1) + G(2) + … + G(n)。这个我们可以用一个sum预先存下前缀和。而F(2) = G(2) + G(4) + …

也即G(1) + G(2) + … + G(n / 2)。

这里可以用莫比乌斯反演。

但是如果每个询问都从1~n这样计算反演，那么由于样例太多，会超时。那么我们可以考虑加一个sqrt(n)的优化。

详见代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1000005;
const LL mod = 1e9 + 7;

LL F[maxn],f[maxn],cnt[maxn],sum[maxn];
LL n;
bool check[maxn];
LL prime[maxn],mu[maxn];
LL sum_mu[maxn];

void mobius(){
    memset(check,false,sizeof(check));
    mu[1] = 1;
    sum_mu[1] = 1;
    int tot = 0;
    for(LL i = 2;i < maxn;++i){
        if(!check[i]){
            prime[tot++] = i;
            mu[i] = -1;
        }
        for(int j = 0;j < tot;++j){
            if(i * prime[j] > maxn) break;
            check[i * prime[j]] = true;
            if(i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                break;
            }
            else mu[i * prime[j]] = -mu[i];
        }
        sum_mu[i] = mu[i] + sum_mu[i - 1];
    }
}
void init(){
    for(LL i = 1;i < maxn;++i){
        for(LL j = 1;i * j < maxn;++j){
            ++cnt[i * j];
        }
    }
    f[1] = F[1] = 1;
    for(LL i = 2;i < maxn;++i){
        F[i] = f[i - 1] + i;
        F[i] %= mod;
        f[i] = (F[i] - i + cnt[i] + mod) % mod;
    }
    for(int i = 1;i < maxn;++i){
        sum[i] = F[i] + sum[i - 1];
    }
}

int main(){
    init();
    mobius();
    while(scanf("%lld",&n) == 1){
        LL ans = 0;
        LL last = 0;
        for(LL i = 1;i <= n;i = last + 1){
            last = n / (n / i);
            ans += (sum_mu[last] - sum_mu[i - 1]) * sum[n / i];
            ans = (ans + mod) % mod;
            //printf("sum[%d / %d] == %lld\n",n,i,sum[n / i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}