牛客练习赛 53B - Dicer's Blog

题目#

题意#

求和式： $\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
#include <bits/stdc++.h>
2

3
using namespace std;
4

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

10
int main () {
11
    for (int i = 1; i <= 3000000; ++i) p[i] = 1;
12
    ll n; cin >> n;
13
    ll ans = 0;
14
    for(ll j = 1; j <= n; ++j) {
15
        ll lim = n/j, l = j, r = min(2 * j - 1, n);
16
        for (ll i = 1; i <= lim; ++i) {
17
            p[i] = p[i] * i % MOD;
18
            ans += (l+r)*(r-l+1)/2%MOD*p[i]%MOD;
19
            ans %= MOD;
20
            l += j; r = min(r + j, n);
21
        }
22
    }
23
    cout << ans << endl;
24
    return 0;
25
}