[题解] Codeforces Round #640 (Div. 4) C题 题解

C. K-th Not Divisible by n

题意

给你一个 n 和 k。

设存在唯一的一个数 \(m\) ,满足 前 \(m\) 个数中有 \(m-k\) 个可以被 \(n\) 整除的数。

如样例:\(n=3, k=7\) ,则答案为 \(m=10\), \(10/3 == 10-7\)

解题思路

由题意可得到一个二分答案的条件:\(m\) 满足:\(m-(m÷n)=k\) 所以说,我们可以二分这个m,范围为 \([0, {10}^{10}]\)(范围胡扯的,没确定范围,就拉满了)

手写二分的话,是枚举第一个大于等于条件的值

AC代码

#include <iostream>
 
using namespace std;
 
typedef long long ll;
 
int solve ( void )
{
    ll n, k;
    cin >> n >> k;
    
    ll l = 0, r = 1e10;
    
    while ( l < r )
    {
        ll mid = l + r >> 1;
        if ( mid - mid / n >= k ) r = mid;
        else l = mid + 1;
    }
    
    return r;
}
int main ( void )
{
    int T;
    cin >> T;
    while ( T-- ) cout << solve() << endl;
    
    return 0;
}

放心。不会超时的。

这是二分写法,还有推公式写法,我数学蒟蒻,就不自残脑细胞了

上一篇:PAT (Advanced Level) Practice 1027 Colors in Mars (20 分)


下一篇:一条关于swap争用的报警邮件分析