目录
一、题目
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;
}