1925B.md (1772B)
1 Source: https://codeforces.com/problemset/problem/1925/B 2 3 B. A Balanced Problemset? 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Jay managed to create a problem of difficulty $x$ and decided to make it the second problem for Codeforces Round #921. 22 23 But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of $n$ sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to $x$. 24 25 The coordinator, Aleksey, defines the balance of a problemset as the [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) of the difficulties of all sub-problems in the problemset. 26 27 Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally. 28 29 Input 30 31 The first line of input contains a single integer $t$ ($1\leq t\leq 10^3$) denoting the number of test cases. 32 33 Each test case contains a single line of input containing two integers $x$ ($1\leq x\leq 10^8$) and $n$ ($1\leq n\leq x$). 34 35 Output 36 37 For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve. 38 39 Example 40 41 Input 42 43 ``` 44 3 45 46 10 3 47 48 5 5 49 50 420 69 51 ``` 52 53 Output 54 55 ``` 56 2 57 1 58 6 59 ``` 60 61 Note 62 63 For the first test case, one possible way is to break up the problem of difficulty $10$ into a problemset having three problems of difficulties $4$, $2$ and $4$ respectively, giving a balance equal to $2$. 64 65 For the second test case, there is only one way to break up the problem of difficulty $5$ into a problemset of $5$ problems with each problem having a difficulty $1$ giving a balance equal to $1$.