Chef and Prime Divisors
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given two positive integers – A and B. You have to check whether A is divisible by all the prime divisors of B.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
For each test case, you are given two space separated integers – A and B.
For each test case, output "Yes" (without quotes) if A contains all prime divisors of B, otherwise print "No".
- 1 ≤ T ≤ 104
- 1 ≤ A, B ≤ 1018
- Subtask 1 (20 points):1 ≤ B ≤ 107
- Subtask 2 (30 points):1 ≤ A ≤ 107
- Subtask 3 (50 points): Original constraints
Input: 3 120 75 128 16 7 8 Output: Yes Yes No
Example case 1. In the first case 120 = 23*3*5 and 75 = 3*52. 120 is divisible by both 3 and 5. Hence, we will print "Yes"
Example case 2. In the second case both 128 and 16 are powers of two. Hence, the answer is "Yes"
Example case 3. In the third case 8 is power of two and 7 is not divisible by 2. So, the answer is "No"
|Tags||basic-math, easy, gcd, may15, witalij_hq|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.