调和级数枚举+dp，CF 822D - My pretty girl Noora

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

822D - My pretty girl Noora

---

二、解题报告

1、思路分析

求和式子中的幂次是固定的，我们只需关注如何求解 f(i)？

经过观察，不难得出：

f(i) = min { f(j) + i / j * (j - 1) * j / 2 }，即 将 i 个人分为 j 组

由于 [0, n] 所有 数的因子个数和为n ln n 级别的，所以我们只需计算n ln n次

但是直接暴力枚举因子是O(NsqrtN)的

我们外层枚举组数i，内层枚举每组人数j，i * j <= n，这就是一个典型的调和级数枚举

本题还能优化到O(N)，但是那个我不会证明了QAQ

2、复杂度

时间复杂度： O(NlnN) 空间复杂度：O(N)

3、代码详解

#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1E-9;
constexpr int P = 1'000'000'007;void solve() {int t, l, r;std::cin >> t >> l >> r;std::vector<i64> f(r + 1, inf64);f[1] = 0;for (int i = 1; i <= r; ++ i) {for (int j = 2; j * i <= r; ++ j) {f[i * j] = std::min(f[i * j], f[i] + 1LL * j * (j - 1) / 2 * i);}}int res = 0;for (int i = l, s = 1; i <= r; ++ i) {f[i] %= P;res = (res + s * f[i] % P) % P;s = 1LL * s * t % P;}std::cout << res << '\n';
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}