栗酱的不等式
栗酱的不等式
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; } }