Codeforces Round #256 (Div. 2)——Multiplication Table

题目链接

  • 题意:

    n*m的一个乘法表,从小到大排序后,输出第k个数

     (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m)
  • 分析:

    对于k之前的数,排名小于k;k之后的数大于,那么就能够採用二分。
LL n, m, k;

LL fun(LL goal)
{
LL t = 0, ret = 0;
while (++t <= m)
{
ret += min(n, goal / t);
}
return ret;
} LL bin(LL L, LL R, LL goal)
{
LL M, V;
while (L <= R)
{
M = (L + R) >> 1;
V = fun(M);
if (V < goal)
L = M + 1;
else
R = M - 1;
}
return L;
} int main()
{
// freopen("in.txt", "r", stdin);
while (cin >> n >> m >> k)
{
cout << bin(1, 1e15, k) << endl;
}
return 0;
}

上一篇:C++中 指针 与 引用 的区别


下一篇:ELK之收集tomcat访问日志