翻译

买铲子

出题者想买 n 个铲子，商店用不同的包裹的卖铲子。商店有 k 种包裹：包裹内的铲子数量为从 1 到 k，每种包裹的数量不限。

出题者想要购买一定数量的一种包裹，一共购买 n 个铲子，并且要求购买最少的包裹。

输入格式

输入整数 t，表示测试用例组数。

每个测试用例输入两个数字 n k，用空格分隔。

输出格式

输出购买包裹的最小数量。

分析

因为 n 和 k 的数量都是 10^9，不能遍历，因为遍历会超时：

因为两个数相乘等于 n，所以这个数字的小端不大于 sqrt(n) + 1，也就是需要遍历 min(sqrt(n) + 1, k) 范围内的整数，判断是否能整除，如果成整除，就将这个数字和除法的结果分别与 k 比较，符合要求的比较大小得到结果。

代码(PyPy3)

# https://codeforces.com/problemset/problem/1360/D

import sys
import os
import heapq
import math

try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass

t = int(input())

def printd(value):
    # print(value)
    pass

for _ in range(t):
    arr = list(map(int, input().split(" ")))
    n, k = arr[0], arr[1]
    result = n
    end = min(k, int(math.sqrt(n)) + 1)
    for i in range(1, end + 1):
        if n % i == 0:
            number = int(n / i)
            if number <= k:
                result = min(result, i)
            if i <= k:
                result = min(number, result)

    print(result)

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

by 费城的二鹏 2020.05.25 长春