题目

题目描述:
有不等式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;
}
//函数区