首页 > 代码库 > Codeforces Round #256 (Div. 2)——Multiplication Table

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

2024-07-12 17:10:55   226人阅读

题目链接

  • 题意：
    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;
}


联系
我们