-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path1360D Buying Shovels.cpp
105 lines (87 loc) · 1.83 KB
/
1360D Buying Shovels.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*
author : MishkatIT
created : Monday 2022-11-14-05.10.33
problem : 1360 D. Buying Shovels
*/
#include<iostream>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main()
{
fio;
int t;
cin >> t;
while(t--)
{
int n, k;
cin >> n >> k;
if(n <= k)
{
cout << 1 << '\n';
continue;
}
int ans = n;
for (int i = 1; i * i <= n; i++)
if (n % i == 0)
{
if (n / i <= k)
ans = min(ans, n / (n / i));
if (i <= k)
ans = min(ans, n / i);
}
cout << ans << '\n';
}
return 0;
}
//TLE
////int isPrime(int n)
////{
//// for (long long i = 2; i * i <= n; i++)
//// {
//// if(n % i == 0)
//// return 0;
//// }
//// return 1; // its placement was wrong, now fixed.
////}
//int main()
//{
// fio;
// int t;
// cin >> t;
// while(t--)
// {
// int n, k;
// cin >> n >> k;
// if(n <= k)
// {
// cout << 1 << '\n';
// continue;
// }
// if(n > k)
// {
//// if(isPrime(n))
//// {
//// cout << n << '\n';
//// continue;
//// }
// bool ok = false;
// for (int i = 2; i <= n; i++)
// {
// if(n % i == 0)
// {
// if(i * k >= n)
// {
// cout << i << '\n';
// break;
// }
// ok = true;
//
// }
// }
// if(!ok)
// cout << n << '\n';
// }
// }
//
// return 0;
//}