LOJ#6491. zrq 学反演(莫比乌斯反演 杜教筛)

题意

题目链接

Sol

反演套路题? 不过最后一步还是挺妙的。

套路枚举\\(d\\)，化简可以得到

\\[\\sum_{T = 1}^m (\\frac{M}{T})^n \\sum_{d \\ | T} d \\mu(\\frac{T}{d})\\]

后面的显然是狄利克雷卷积的形式，但是这里\\(n \\leqslant 10^{11}\\)显然不能直接线性筛了

设\\(F(n) = n, f(n) = \\phi(n)\\)

根据欧拉函数的性质，有\\(F(n) = \\sum_{d \\ | n} f(d)\\)

反演一下

\\[f(n) = \\sum_{d \\ | n} \\mu(d) F(\\frac{n}{d})\\]

\\[\\phi(n) = \\sum_{d \\ |n} d \\mu(\\frac{n}{d})\\]

那么原式等于

\\[\\sum_{T = 1}^m (\\frac{M}{T})^n \\phi(T)\\]

然后杜教筛+数论分块一波

注意线性筛的范围最好设大一点

#include<bits/stdc++.h>
#define ull unsigned long long
#define LL long long  
using namespace std;
const int MAXN = 1e7 + 10;
LL N, M, Lim;
int vis[MAXN], prime[MAXN], tot;
ull mp[MAXN], phi[MAXN];
void get(int N) {
    vis[1] = phi[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
        for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) {phi[i * prime[j]] = phi[i] * prime[j]; break;}
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for(int i = 2; i <= N; i++) phi[i] += phi[i - 1];
}
ull mul(ull x, ull y) {
    return  x * y;
}
ull fp(ull a, ull p) {
    ull   = 1;
    while(p) {
        if(p & 1)   = mul( , a);
        a = mul(a, a); p >>= 1;
    }
    return  ;
}
ull S(LL x) {
    if(x <= Lim) return phi[x];
    else if(mp[M / x]) return mp[M / x];
    ull rt;
    rt = (x & 1) ? (x + 1) / 2 * (x) : (x / 2) * (x + 1);
    //rt = (x + 1) * x / 2;
    for(LL d = 2, nxt; d <= x; d = nxt + 1) {
        nxt = x / (x / d);
        rt -= (nxt - d + 1) * S(x / d);
    }
    return mp[M / x] = rt;
}
signed main() {
    cin >> N >> M;
    get(Lim = ((int)1e7)); 
    //for(int i = 1; i <= M; i++) printf("%d ", phi[i]);
    ull ans = 0;
    for(LL i = 1, nxt; i <= M; i = nxt + 1) {
        nxt = M / (M / i);
        ans += fp(M / i, N) * (S(nxt) - S(i - 1));
      //  cout << i << '\\n';
    }
    cout << ans;
    return 0;
}