CFR-644D Buying Shovels 题解

题目大意

你需要买n个东西，给你k个数$1-K$,代表你能一次买k个，你需要选择一个数，且只能选择一个数，让次数最少。

解题思路

服了。。

写的时候真的觉得自己可能是智障。。

愣是卡死在这个题目了。

明明纯暴力水题。。

吐了。

（还是自己太菜了。。哭

对于n来说，假设存在某个数i，能使n整除i，那么代价就是$min(i,n/i)$。

那么我只需要找到最小的i即可。

遍历的范围只需要从1到sqrt(n)即可。

注意还要考虑另一边。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;

int check(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)	return 0;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		if (k >= n) {
			cout << 1 << endl;
			continue;
		}
		int ans = n;
		for (int i = 2; i*i<=n; i++) {
			if (n % i == 0) {
				if (n / i <= k) {
					ans = min(ans,i);
					break;
				}
				if (i <= k) {
					ans = min(ans, n / i);
				}
			}
		}
		cout << ans << endl;
	}
}