【2020杭电多校第六场】 6833 Very Easy Math Problem

【2020杭电多校第六场】 6833 Very Easy Math Problem 莫比乌斯反演

题意思路Code（2121MS）

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6833

借鉴大佬： https://blog.csdn.net/weixin_44282912/article/details/107844614 https://blog.csdn.net/oampamp1/article/details/107865300

题意

$$求解\sum _{a_1=1}^n\sum _{a_2=1}^n...\sum _{a_x=1}^n\left(\prod _{j=1}^x{a}_j^k\right)f(gcd(a_1,a_2...a_x))gcd(a_1,a_2...a_x)$$

思路

$令d=gcd(a_1,a_2...a_x)得：$

$$\sum _{a_1=1}^n\sum _{a_2=1}^n...\sum _{a_x=1}^n\left(\prod _{j=1}^x{a}_j^k\right)f(d)d$$

$枚举d得：$

$$\sum _{d=1}^{n}df(d)\sum _{a_1=1}^n\sum _{a_2=1}^n...\sum _{a_x=1}^n\left(\prod _{j=1}^x{a}_j^k\right)[gcd(a_1,a_2...a_x)=d]$$

$$\sum _{d=1}^n{d}^{kx+1}f(d)\sum _{a_1=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{a_2=1}^{\lfloor \frac{n}{d}\rfloor }...\sum _{a_x=1}^{\lfloor \frac{n}{d}\rfloor }\left(\prod _{j=1}^x{a}_j^k\right)[gcd(a_1,a_2...a_x)=1]$$

$$\sum _{d=1}^n{d}^{kx+1}f(d)\sum _{a_1=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{a_2=1}^{\lfloor \frac{n}{d}\rfloor }...\sum _{a_x=1}^{\lfloor \frac{n}{d}\rfloor }\left(\prod _{j=1}^x{a}_j^k\right)\sum _{t|a_{1}t|a2...t|a_x}\mu (t)$$

$$\sum _{d=1}^n{d}^{kx+1}f(d){\left(\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }{i}^k\right)}^x\sum _{t|a_{1}t|a2...t|a_x}\mu (t)$$

$枚举t得：$

$$\sum _{d=1}^n{d}^{kx+1}f(d)\sum _{t=1}^{\lfloor \frac{n}{d}\rfloor }\mu (t){\left(\sum _{i=1}^{\lfloor \frac{n}{dt}\rfloor }(it{)}^k\right)}^x$$

$$\sum _{d=1}^n{d}^{kx+1}f(d)\sum _{t=1}^{\lfloor \frac{n}{d}\rfloor }\mu (t)t^{kx}{\left(\sum _{i=1}^{\lfloor \frac{n}{dt}\rfloor }{i}^k\right)}^x$$

$令T=dt并枚举T得：$

$$\sum _{T=1}^n{\left(\sum _{i=1}^{\lfloor \frac{n}{dt}\rfloor }{i}^k\right)}^x{T}^{kx}\sum _{d|T}df(d)\mu (\frac{T}{d})$$

$令g(T)={\sum }_{d|T}df(d)\mu (\frac{T}{d})，则$

$$\sum _{T=1}^n{\left(\sum _{i=1}^{\lfloor \frac{n}{T}\rfloor }{i}^k\right)}^x{T}^{kx}g(T)$$

$O(nlogn)筛f和g，并对T^{kx}g(T)和{\sum }_{i=1}^{\lfloor \frac{n}{T}\rfloor }{i}^k做前缀和，最后\sqrt{n}分块计算，复杂度为O(nlogn+T\sqrt{n})$

Code（2121MS）

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pdd; #define INF 0x3f3f3f3f #define lowbit(x) x & (-x) #define mem(a, b) memset(a , b , sizeof(a)) #define FOR(i, x, n) for(int i = x;i <= n; i++) // const ll mod = 998244353; const ll mod = 1e9 + 7; // const double eps = 1e-6; // const double pi = acos(-1); const int N = 2e5 + 10; ll T, k, x; int mu[N]; // 莫比乌斯函数 bool is_prime[N]; int prime[N]; int cnt; ll g[N], f[N]; ll sumG[N], sumi[N]; ll quick_pow(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans % mod; } void Mobi() // 莫比乌斯函数初始化 { f[1] = mu[1] = 1; is_prime[0] = is_prime[1] = true; for(int i = 2;i < N; i++) { f[i] = 1; if (!is_prime[i]) { mu[i] = -1; prime[++cnt] = i; } for (int j = 1; j <= cnt && i * prime[j] < N; j++) { is_prime[i * prime[j]] = true; if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } mu[i * prime[j]] = -mu[i]; } } // 筛f函数 for(int d = 2;d * d < N; d++) { for(int i = d * d;i < N; i += d * d) { f[i] = 0; } } // 筛g函数 for(int d = 1;d < N; d++) { for(int i = d;i < N; i += d) { g[i] = (g[i] + 1ll * d * f[d] % mod * mu[i / d] % mod + mod) % mod; } } // 处理sumG函数和sumi函数前缀和 for(int i = 1;i < N; i++) { ll t = quick_pow(i, k); sumi[i] = (sumi[i - 1] + t) % mod; sumG[i] = (sumG[i - 1] + quick_pow(t, x) * g[i] % mod) % mod; } } void solve() { cin >> T >> k >> x; Mobi(); while(T--) { int n; cin >> n; ll ans = 0; for(int l = 1, r;l <= n; l = r + 1) { r = min(n, n / (n / l)); ans = (ans + (sumG[r] - sumG[l - 1] + mod) % mod * quick_pow(sumi[n / l], x) % mod) % mod; } cout << ans << endl; } } signed main() { ios_base::sync_with_stdio(false); //cin.tie(nullptr); //cout.tie(nullptr); #ifdef FZT_ACM_LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); signed test_index_for_debug = 1; char acm_local_for_debug = 0; do { if (acm_local_for_debug == '$') exit(0); if (test_index_for_debug > 20) throw runtime_error("Check the stdin!!!"); auto start_clock_for_debug = clock(); solve(); auto end_clock_for_debug = clock(); cout << "Test " << test_index_for_debug << " successful" << endl; cerr << "Test " << test_index_for_debug++ << " Run Time: " << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl; cout << "--------------------------------------------------" << endl; } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug)); #else solve(); #endif return 0; }