题目

题目描述：
有不等式y⋅x3≤ n，已知y为正整数，x为大于1的正整数，问当x和y的解数量刚好为m的时候n的最小值，如果不存在输出 -1。
输入描述：
多组数据读入。
每组数据一个数字m，如题所示。

输出描述：
每组数据输出一行，输出答案。

解析

1）知识点

  • 这道题是一道二分的题目。

2）看题目

  • 首先看题，就是说我们给定解的数量，求最小的n。

3）算法分析

  1. 我们求解，首先写成函数的形式y = n / x3。
  2. 然后用二分法查找答案，假设答案是mid，那么我们要统计mid有多少种解，就设定一个循环，让x从2到n（范围题目有）进行累加。
  3. 如果统计数量比想要的多，就删右界。少就删左界。如果正好相等，就表示和题目说的一样，数量刚好为m，就标记答案就好了。

4）算法操作

  1. 首先就是经典的二分模板： 
    while (l <= r) {
    ll mid = l + r >> 1;
    if (judge(mid)) {
        r = mid - 1;
    }
    else l = mid + 1;
}
  2. 然后和上面说的一样，我们要对答案进行统计： 
    ll judge(ll x) {
    ll cnt = 0;
    for (ll i = 2; i * i * i <= x; i++)
        cnt += x / (i * i * i);
    //求出y的组数
    return cnt;
}
  3. 我们这里用函数进行统计，所以在外面进行判断，同时标记答案： 
    ll cnt = judge(mid);
    if (cnt >= n) {
        r = mid - 1;
        if (cnt == n) ans = mid;
    }
    else l = mid + 1;
  4. 就按此进行二分就好了，因为答案不符合要求就要输出-1，那么把ans初始化为-1就好了（不符合要求就不会改变）。

5）打代码

  1. 首先就是多组输入。
  2. 然后开始按照上面讲的二分。
  3. 下面全代码~

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;
}
//函数区