1444A.md (1669B)
1 Source: https://codeforces.com/problemset/problem/1444/A 2 3 A. Division 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division. 22 23 To improve his division skills, Oleg came up with $t$ pairs of integers $p_i$ and $q_i$ and for each pair decided to find the greatest integer $x_i$, such that: 24 25 * $p_i$ is divisible by $x_i$; 26 * $x_i$ is not divisible by $q_i$. 27 28 Oleg is really good at division and managed to find all the answers quickly, how about you? 29 30 Input 31 32 The first line contains an integer $t$ ($1 \le t \le 50$) — the number of pairs. 33 34 Each of the following $t$ lines contains two integers $p_i$ and $q_i$ ($1 \le p_i \le 10^{18}$; $2 \le q_i \le 10^{9}$) — the $i$-th pair of integers. 35 36 Output 37 38 Print $t$ integers: the $i$-th integer is the largest $x_i$ such that $p_i$ is divisible by $x_i$, but $x_i$ is not divisible by $q_i$. 39 40 One can show that there is always at least one value of $x_i$ satisfying the divisibility conditions for the given constraints. 41 42 Example 43 44 Input 45 46 ``` 47 3 48 10 4 49 12 6 50 179 822 51 ``` 52 53 Output 54 55 ``` 56 10 57 4 58 179 59 ``` 60 61 Note 62 63 For the first pair, where $p_1 = 10$ and $q_1 = 4$, the answer is $x_1 = 10$, since it is the greatest divisor of $10$ and $10$ is not divisible by $4$. 64 65 For the second pair, where $p_2 = 12$ and $q_2 = 6$, note that 66 67 * $12$ is not a valid $x_2$, since $12$ is divisible by $q_2 = 6$; 68 * $6$ is not valid $x_2$ as well: $6$ is also divisible by $q_2 = 6$. 69 70 The next available divisor of $p_2 = 12$ is $4$, which is the answer, since $4$ is not divisible by $6$.