2020B.md (2567B)
1 Source: https://codeforces.com/problemset/problem/2020/B 2 3 B. Brightness Begins 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 Imagine you have $n$ light bulbs numbered $1, 2, \ldots, n$. Initially, all bulbs are on. To flip the state of a bulb means to turn it off if it used to be on, and to turn it on otherwise. 22 23 Next, you do the following: 24 25 * for each $i = 1, 2, \ldots, n$, flip the state of all bulbs $j$ such that $j$ is divisible by $i^\dagger$. 26 27 After performing all operations, there will be several bulbs that are still on. Your goal is to make this number exactly $k$. 28 29 Find the smallest suitable $n$ such that after performing the operations there will be exactly $k$ bulbs on. We can show that an answer always exists. 30 31 $^\dagger$ An integer $x$ is divisible by $y$ if there exists an integer $z$ such that $x = y\cdot z$. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 The only line of each test case contains a single integer $k$ ($1 \le k \le 10^{18}$). 38 39 Output 40 41 For each test case, output $n$ — the minimum number of bulbs. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 50 1 51 52 3 53 54 8 55 ``` 56 57 Output 58 59 ``` 60 2 61 5 62 11 63 ``` 64 65 Note 66 67 In the first test case, the minimum number of bulbs is $2$. Let's denote the state of all bulbs with an array, where $1$ corresponds to a turned on bulb, and $0$ corresponds to a turned off bulb. Initially, the array is $[1, 1]$. 68 69 * After performing the operation with $i = 1$, the array becomes $[\underline{0}, \underline{0}]$. 70 * After performing the operation with $i = 2$, the array becomes $[0, \underline{1}]$. 71 72 In the end, there are $k = 1$ bulbs on. We can also show that the answer cannot be less than $2$. 73 74 In the second test case, the minimum number of bulbs is $5$. Initially, the array is $[1, 1, 1, 1, 1]$. 75 76 * After performing the operation with $i = 1$, the array becomes $[\underline{0}, \underline{0}, \underline{0}, \underline{0}, \underline{0}]$. 77 * After performing the operation with $i = 2$, the array becomes $[0, \underline{1}, 0, \underline{1}, 0]$. 78 * After performing the operation with $i = 3$, the array becomes $[0, 1, \underline{1}, 1, 0]$. 79 * After performing the operation with $i = 4$, the array becomes $[0, 1, 1, \underline{0}, 0]$. 80 * After performing the operation with $i = 5$, the array becomes $[0, 1, 1, 0, \underline{1}]$. 81 82 In the end, there are $k = 3$ bulbs on. We can also show that the answer cannot be smaller than $5$.