[题解] 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;
}

放心。不会超时的。

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