题目
题目描述:有不等式y⋅x3≤ n,已知y为正整数,x为大于1的正整数,问当x和y的解数量刚好为m的时候n的最小值,如果不存在输出 -1。
输入描述:
多组数据读入。每组数据一个数字m,如题所示。
输出描述:
每组数据输出一行,输出答案。
解析
1)知识点
- 这道题是一道二分的题目。
2)看题目
- 首先看题,就是说我们给定解的数量,求最小的n。
3)算法分析
- 我们求解,首先写成函数的形式y = n / x3。
- 然后用二分法查找答案,假设答案是mid,那么我们要统计mid有多少种解,就设定一个循环,让x从2到n(范围题目有)进行累加。
- 如果统计数量比想要的多,就删右界。少就删左界。如果正好相等,就表示和题目说的一样,数量刚好为m,就标记答案就好了。
4)算法操作
- 首先就是经典的二分模板:
while (l <= r) { ll mid = l + r >> 1; if (judge(mid)) { r = mid - 1; } else l = mid + 1; }
- 然后和上面说的一样,我们要对答案进行统计:
ll judge(ll x) { ll cnt = 0; for (ll i = 2; i * i * i <= x; i++) cnt += x / (i * i * i); //求出y的组数 return cnt; }
- 我们这里用函数进行统计,所以在外面进行判断,同时标记答案:
ll cnt = judge(mid); if (cnt >= n) { r = mid - 1; if (cnt == n) ans = mid; } else l = mid + 1;
- 就按此进行二分就好了,因为答案不符合要求就要输出-1,那么把ans初始化为-1就好了(不符合要求就不会改变)。
5)打代码
- 首先就是多组输入。
- 然后开始按照上面讲的二分。
- 下面全代码~
AC代码
#include <iostream> using namespace std; typedef long long ll; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const ll INF = 0x3f3f3f3f3f3f3f3f; //全局变量区 ll judge(ll x) { ll cnt = 0; for (ll i = 2; i * i * i <= x; i++) cnt += x / (i * i * i); //求出y的组数 return cnt; } //函数预定义区 int main() { IOS; ll n; while (cin >> n) { ll ans = -1, l = 8, r = INF; while (l <= r) { ll mid = l + r >> 1; ll cnt = judge(mid); if (cnt >= n) { r = mid - 1; if (cnt == n) ans = mid; } else l = mid + 1; } cout << ans << endl; } return 0; } //函数区