codeforces-scrape

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

2238D.md (2512B)


      1 Source: https://codeforces.com/problemset/problem/2238/D
      2 
      3 D. Storming Arasaka
      4 
      5 time limit per test
      6 
      7 2 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 Hah, you just discovered what it takes to become a legend.
     22 
     23 — Cyberpunk 2077
     24 
     25 You and Johnny Silverhand decided to storm Arasaka together. After making your way through the guards, you reached Mikoshi — but in order to connect to it, you need to hack the main server.
     26 
     27 The password to the server is formed as follows. There is a secret number $n$. Consider all of its positive divisors except $1$, but the divisor equal to  $\mathbf{n}$  is considered, and partition all of them into several nonempty layers $L_1, L_2, \ldots, L_k$. A partition is called good if two conditions are satisfied:
     28 
     29 * for any divisor $x$ from layer $L_i$, all of its divisors, except $1$ and $x$, lie only in the layers $L_1, L_2, \ldots, L_{i-1}$;
     30 * in each layer, all numbers can be ordered into a chain so that any two neighboring numbers in this chain have GCD$^{\text{∗}}$ greater than $1$.
     31 
     32 The length of the password is defined as the number of layers $k$. For the security of the layers, their number must be as small as possible.
     33 
     34 Fortunately, Arasaka has not changed $n$ since Johnny's time, and he remembers several possible values of this number. For each of them, help V and Johnny determine the minimum possible number of layers.
     35 
     36 $^{\text{∗}}$$\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$.
     37 
     38 Input
     39 
     40 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.
     41 
     42 The only line of each test case contains a single integer $n$ ($2 \le n \le 10^6$) — a candidate value of the secret number that Johnny told you.
     43 
     44 Output
     45 
     46 For each test case, output a single number — the minimum number of layers.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 8
     54 
     55 2
     56 
     57 4
     58 
     59 8
     60 
     61 16
     62 
     63 32
     64 
     65 67
     66 
     67 120
     68 
     69 33
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 1
     76 
     77 2
     78 
     79 3
     80 
     81 4
     82 
     83 5
     84 
     85 1
     86 
     87 7
     88 
     89 3
     90 ```
     91 
     92 Note
     93 
     94 In the first $5$ test cases, the given number has the form $2^k$. Let us show that the answer for them is $k$. Consider all positive divisors except $1$: $2^1, 2^2, \ldots, 2^{k}$. It is clear that no two of them can lie in the same layer, which means that all of them lie in different layers. An example of an arrangement is: $L_i = \{2^i\}$. It is clear that it satisfies the conditions, and exactly $k$ layers are obtained.