c/c++语言开发共享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 base = 1;     while(p) {         if(p & 1) base = mul(base, a);         a = mul(a, a); p >>= 1;     }     return base; } 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; }