二分+数学，CF 689C - Mike and Chocolate Thieves

本文主要是介绍二分+数学，CF 689C - Mike and Chocolate Thieves，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

689C - Mike and Chocolate Thieves

---

二、解题报告

1、思路分析

考虑一个长度为4的等比数列，ak, ak, ak^2, ak^3

ak^3 <= m

a <= m / k^3

也就是说，上界不超过m，公比为k，的长度为4的等比数列的个数为 m / k^3

那么我们二分m

check 累计数目是否合法即可

2、复杂度

时间复杂度： O(m^(1/3) log m)空间复杂度：O(1)

3、代码详解

 ​

#include <bits/stdc++.h>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 998'244'353;void solve() {i64 m;std::cin >> m;auto f = [&](i64 x) -> i64 {i64 s = 0;for (i64 i = 2; i * i * i <= x; ++ i)s += x / (i * i * i);return s;};i64 lo = 1, hi = m * 8;while (lo < hi) {i64 x = lo + (hi - lo) / 2;if (f(x) >= m) hi = x;else lo = x + 1;}if (f(hi) == m)std::cout << hi;elsestd::cout << -1;
}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);#endifint T = 1;// std::cin >> T;while (T --)solve();return 0;
}

这篇关于二分+数学，CF 689C - Mike and Chocolate Thieves的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---