目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

325B - Stadium and Games

---

二、解题报告

1、思路分析

考虑 一个可能的初始队伍数目 num 的 变化历程

除2，除2，除2 ……=> 变为 奇数m，m * (m - 1) / 2

假如除了 i 次2，变为奇数m

那么有 m * (2^i - 1) + (m - 1) * m / 2 = n

因为指数增长很快，2^60 都已经超过1E18了

我们发现合法的 i 其实很少

而一旦 i 固定，式子关于 m 就是单调递增的

于是想到 枚举 i，二分 m

问题迎刃而解

2、复杂度

时间复杂度： O(log^2 n)空间复杂度：O(1)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;void solve() {i64 n;std::cin >> n;bool f = 0;for (int i = 0; i < 60; ++ i) {i64 v = 1LL << i;i64 lo = 0, hi = std::min(1LL << 31, n / std::max(v - 1, 1LL));while (lo < hi) {i64 x = lo + (hi - lo) / 2;if (x * (v - 1) + x * (x - 1) / 2 >= n) hi = x;else lo = x + 1;}if (hi * (v - 1) + hi * (hi - 1) / 2 == n && (hi & 1)) {std::cout << hi * v << '\n';f = true;}}if (!f) std::cout << "-1\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}