题意
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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605921.html