传送门: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}^xa_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}^xa_j^k\right)f(d)d$$
$枚举d得:$
$$\sum_{d=1}^ndf(d)\sum_{a_1=1}^n\sum_{a_2=1}^n…\sum_{a_x=1}^n\left(\prod_{j=1}^xa_j^k\right)[gcd(a_1,a_2…a_x)=d]$$
$$\sum_{d=1}^nd^{kx+1}f(d)\sum_{a_1=1}^{\left \lfloor \frac{n}{d} \right \rfloor }\sum_{a_2=1}^{\left \lfloor \frac{n}{d} \right \rfloor }…\sum_{a_x=1}^{\left \lfloor \frac{n}{d} \right \rfloor }\left(\prod_{j=1}^xa_j^k\right)[gcd(a_1,a_2…a_x)=1]$$
$$\sum_{d=1}^nd^{kx+1}f(d)\sum_{a_1=1}^{\left \lfloor \frac{n}{d} \right \rfloor }\sum_{a_2=1}^{\left \lfloor \frac{n}{d} \right \rfloor }…\sum_{a_x=1}^{\left \lfloor \frac{n}{d} \right \rfloor }\left(\prod_{j=1}^xa_j^k\right)\sum_{ta_1\;ta2\;…\;ta_x}\mu(t)$$
$$\sum_{d=1}^nd^{kx+1}f(d)\left (\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor }i^k\right)^x\sum_{ta_1\;ta2\;…\;ta_x}\mu(t)$$
$枚举t得:$
$$\sum_{d=1}^nd^{kx+1}f(d)\sum_{t=1}^{\left \lfloor \frac{n}{d} \right \rfloor }\mu(t)\left (\sum_{i=1}^{\left \lfloor \frac{n}{dt} \right \rfloor }(it)^k\right)^x$$
$$\sum_{d=1}^nd^{kx+1}f(d)\sum_{t=1}^{\left \lfloor \frac{n}{d} \right \rfloor }\mu(t)t^{kx}\left (\sum_{i=1}^{\left \lfloor \frac{n}{dt} \right \rfloor }i^k\right)^x$$
$令T=dt并枚举T得:$
$$\sum_{T=1}^n\left (\sum_{i=1}^{\left \lfloor \frac{n}{dt} \right \rfloor }i^k\right)^xT^{kx}\sum_{dT}df(d)\mu(\frac{T}{d})$$
$令g(T)=\sum_{dT}df(d)\mu(\frac{T}{d}),则$
$$\sum_{T=1}^n\left (\sum_{i=1}^{\left \lfloor \frac{n}{T} \right \rfloor }i^k\right)^xT^{kx}g(T)$$
$O(nlogn)筛f和g,并对T^{kx}g(T)和\sum_{i=1}^{\left \lfloor \frac{n}{T} \right \rfloor }i^k做前缀和,最后\sqrt n分块计算,复杂度为O(nlogn+T\sqrt n)$
Code(2121MS)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
| ##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 = 1e9 + 7;
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]; } } for(int d = 2;d * d < N; d++) { for(int i = d * d;i < N; i += d * d) { f[i] = 0; } } 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; } } 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); ##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; }
|
本文作者:jujimeizuo
本文地址: https://blog.jujimeizuo.cn/2020/10/07/hdu-6833/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!