牛客练习赛-53B

牛客练习赛-53B

题目

题目链接

题意

求和式: $$\sum_{i=1}^{n}{\sum_{j=1}^{i}{i \lfloor {\frac{i}{j}} \rfloor ^j}}$$

分析

更换一下枚举顺序:

$$\sum_{j=1}^{n}\sum_{i=j}^{n}{i \lfloor \frac{i}{j} \rfloor ^ j}$$

可以发现 $i$ 在 区间 $[k\cdot j, (k+1)\cdot j-1]$ 内 $\lfloor \frac{i}{j} \rfloor = k$ ,因此可以对每个 $j$ 做分段处理,另外 $\lfloor \frac{i}{j} \rfloor ^ j$ 可以从上一个状态转移过来。

时间复杂度: $O(n \log n)$

代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 3e6 + 7;
const int MOD = 1e9 + 7;
ll p[MAXN];

int main () {
for (int i = 1; i <= 3000000; ++i) p[i] = 1;
ll n; cin >> n;
ll ans = 0;
for(ll j = 1; j <= n; ++j) {
ll lim = n/j, l = j, r = min(2 * j - 1, n);
for (ll i = 1; i <= lim; ++i) {
p[i] = p[i] * i % MOD;
ans += (l+r)*(r-l+1)/2%MOD*p[i]%MOD;
ans %= MOD;
l += j; r = min(r + j, n);
}
}
cout << ans << endl;
return 0;
}
# 分块

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×