codeforces-scrape

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

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