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;
}
放心。不会超时的。
这是二分写法,还有推公式写法,我数学蒟蒻,就不自残脑细胞了