2017年浙江工业大学大学生程序设计迎新赛决赛 F 栗酱的不等式

发表于 | 分类于 | 浏览 次

题目描述

有不等式 $y\times x^3\le n$ ，已知 $y$ 为正整数，$x$ 为大于1的正整数，问当 $x$ 和 $y$ 的解数量刚好为 $m$ 的时候 $n$ 的最小值，如果不存在输出-1。

题解

观察到，答案是连续的（即随$m$增大，$n$也增大），同时对某个具体的$n$求出解数很容易，应由此想到二分答案$n$。对每一次二分中的$n$，枚举$x$,对每个$x$,有 $\lfloor {n\over x^3} \rfloor$种解数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
#include <algorithm>
#include "iostream"
#include <cmath>
#include <vector>
#include "set"
#include "queue"
using namespace std;
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
typedef long long ll;
const ll INF = 1e18;
const ll MAXN = 5000+100;
const ll MOD = 1e9+7;

ll p3(ll a)
{
    return a*a*a;
}
int main(int argc, char const *argv[]) {
    ll m;
    while(cin>>m)
    {
        ll ans=-1;
        ll l=8,r=INF;
        while(l<=r)
        {
            ll num=0,mid=(l+r)/2;
            // printf("%lld %lld %lld\n", l,r,mid);
            for(int i=2;i<INF && mid/p3(i);++i)
                num+=mid/p3(i);
            if(num==m) ans=mid;
            if(num<m) l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}