Codeforces 1352C - K-th Not Divi

蔚蓝的天空，依稀记得那加班的日子。

翻译

给你两个数字 n 和 k，输出第 k 个不能被 n 整除的数字。

输入格式

第一行输入 t，表示用例组数。

接下来每行是一个用例，包含 n 和 k，用空格分隔。

输出格式

每个测试用例输出一行数字，也即是第 k 个可以被 n 整除的数字。

分析

这道题官方给的解法是 二分法。

我做完之后感觉很有道理，直接二分法查找每个数字是不是满足条件，如果大了就往左搜，小了就往右搜，时间复杂度大概是log(n)，可以满足这个数据量的要求。

我选择了构建公式的方式，int(k / (n - 1)) * n + (-1 if k % (n - 1) == 0 else k % (n - 1))，int(k / (n - 1)) 就是在计算需要多少个 n 才能构建出这个大小的数字，第二部分 (-1 if k % (n - 1) == 0 else k % (n - 1)) 就是在补全余数的大小，如果余数能被整除，说明前面构造的是恰巧被整除需要减一，其余情况添加上余数的值即可。

代码(PyPy3)

# https://codeforces.com/problemset/problem/1352/C

import sys

# sys.stdin = open(r"./file/input.txt", 'r')
# sys.stdout = open(r"./file/output.txt", 'w')

t = int(input())

for _ in range(t):
    arr = input().split(" ")
    n = int(arr[0])
    k = int(arr[1])

    print(int(k / (n - 1)) * n  + (-1 if k % (n - 1) == 0 else k % (n - 1)))

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.05.11 长春