栗酱的不等式

栗酱的不等式

https://ac.nowcoder.com/acm/problem/14696

二分、枚举

题意:
有不等式y*x^3≤ n,已知y为正整数,x为大于1的正整数,问当x和y的解数量刚好为m的时候n的最小值,如果不存在输出 -1。
1<=m<=1e16

利用二分法解决问题,对于任意一个数m
若存在一个数n使得yx^3<=n的解刚好为m个,那么n一定在8到8m之间(因为x>=2)

所以我们的思路便是在8到8m之间进行二分搜索,
对于l,r,mid。
如果n = mid时其解数目大于等于m则意味着我们可能取大了,也可能正好。令r = mid-1;
反之若解数目小于m意味着我们一定取小了则让l = mid+1;
最后,若有正确答案则一定是r+1,再进行一次判断是否 n = r+1时,解的数目正好为m
如若不是输出-1,是输出r+1

那么,如何计算解的个数呢?
暴力枚举。。。。。。。
因为x是三次方所以就很是方便,枚举x用n除,相加。

下面是代码,注意细节

#include<iostream>;
#include<algorithm>;
typedef long long ll;
using namespace std;
ll m;

ll h(ll n) {
    //y*x^3<=n
    ll ans = 0;
    for (ll x = 2;x * x * x <= n;x++)
        ans+=n/(x*x*x);
    return ans;
}

ll solve() {
    ll l = 8;ll r = 1e16;ll mid;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (h(mid)>=m)r = mid - 1;
        else l = mid + 1;
    }
    if (h(r + 1) == m)return r+1;
    else return -1;
}

int main() {
    ios::sync_with_stdio(0);
    while (cin >> m) {
        cout << solve() << endl;
    }
}
全部评论

相关推荐

头像
11-07 01:12
重庆大学 Java
精致的小松鼠人狠话不多:签哪了哥
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务