codeforces-scrape

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

1476A.md (1373B)


      1 Source: https://codeforces.com/problemset/problem/1476/A
      2 
      3 A. K-divisible Sum
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given two integers $n$ and $k$.
     22 
     23 You should create an array of $n$ positive integers $a_1, a_2, \dots, a_n$ such that the sum $(a_1 + a_2 + \dots + a_n)$ is divisible by $k$ and maximum element in $a$ is minimum possible.
     24 
     25 What is the minimum possible maximum element in $a$?
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     30 
     31 The first and only line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^9$; $1 \le k \le 10^9$).
     32 
     33 Output
     34 
     35 For each test case, print one integer — the minimum possible maximum element in array $a$ such that the sum $(a_1 + \dots + a_n)$ is divisible by $k$.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 4
     43 1 5
     44 4 3
     45 8 8
     46 8 17
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 5
     53 2
     54 1
     55 3
     56 ```
     57 
     58 Note
     59 
     60 In the first test case $n = 1$, so the array consists of one element $a_1$ and if we make $a_1 = 5$ it will be divisible by $k = 5$ and the minimum possible.
     61 
     62 In the second test case, we can create array $a = [1, 2, 1, 2]$. The sum is divisible by $k = 3$ and the maximum is equal to $2$.
     63 
     64 In the third test case, we can create array $a = [1, 1, 1, 1, 1, 1, 1, 1]$. The sum is divisible by $k = 8$ and the maximum is equal to $1$.