题意：

已知\(N^2-3N+2=\sum_{d|N}f(d)\)，求\(\sum_{i=1}^nf(i) \mod 1e9+7\)，\(n\leq1e9\)

思路：

杜教筛基础题？

很显然这里已经设了一个\(F(n) = \sum_{d|n}f(d)\)，那么由莫比乌斯反演可以得到\(f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\)。

然后卷积可以看出卷一个\(I\)比较好，则：\((f*g)(n)=\sum_{i=1}^nF(i)-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)\)。显然\(F(i)\)前缀可以通过平方和公式等推出来。那么直接递归做即可。

代码：

#include<map>

#include<set>

#include<cmath>

#include<cstdio>

#include<stack>

#include<ctime>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int maxn = 1e6 + 5;

const ll MOD = 1e9 + 7;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

int mu[maxn], vis[maxn];

int prime[maxn], cnt;

ll sum[maxn];

ll F(ll x){

    return (1LL * x * x - 3 * x + 2) % MOD;

}

void getmu(int n){

    memset(vis, 0, sizeof(vis));

    cnt = 0;

    mu[1] = 1;

    for(int i = 2; i <= n; i++) {

        if(!vis[i]){

            prime[cnt++] = i;

            mu[i] = -1;

        }

        for(int j = 0; j < cnt && prime[j] * i <= n; j++){

            vis[prime[j] * i] = 1;

            if(i % prime[j] == 0){

                mu[i * prime[j]] = 0;

                break;

            }

            mu[i * prime[j]] = -mu[i];

        }

    }

    for(int i = 1; i <= n; i++){

        for(int j = i; j <= n; j += i){

            sum[j] = (sum[j] + mu[i] * F(j / i)) % MOD;

        }

        sum[i] = (sum[i] + sum[i - 1]) % MOD;

    }

}

int N = 1e6;

map<int, ll> mm;

ll ksc(ll a, ll b, ll p){

    ll t = a * b - (ll)((long double)a * b / p + 0.5) * p;

    return (t < 0)? t + p : t;

}

ll inv6 = 166666668, inv2 = 500000004;

ll solve(ll n){

    if(n <= N) return sum[n];

    if(mm.find(n) != mm.end()) return mm[n];

    ll ans = ksc(ksc(n, n + 1, MOD), 2 * n + 1, MOD) * inv6 % MOD;

    ans = (ans - ksc(n, n + 1, MOD) * inv2 % MOD * 3) % MOD;

    ans += 2LL * n;

    ans %= MOD;

    for(int l = 2, r; l <= n; l = r + 1){

        r = n / (n / l);

        ans -= 1LL * (r - l + 1) * solve(n / l);

        ans %= MOD;

    }

    return mm[n] = ans;

}

ll ppow(ll a, ll b, ll p){

    ll ret = 1;

    while(b){

        if(b & 1) ret = ret * a % p;

        a = a * a % p;

        b >>= 1;

    }

    return ret;

}

int main(){

    int T;

    getmu(N);

//    printf("* %lld\n", sum[N + 1]);

    scanf("%d", &T);

    mm.clear();

    while(T--){

        ll n;

        scanf("%lld", &n);

        printf("%lld\n", (solve(n) + MOD) % MOD);

    }

    return 0;

}

巴特西

HDU 5608 function（莫比乌斯反演 + 杜教筛）题解

题意：

思路：

代码：

最新文章

热门文章