codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.