PUCMMT02 - Square-Free Product (Hard)

no tags 

Integer X is Square-Free if and only if p2 (p is prime) does not divide it. For example, 15 is a square-free number but 12 isn't, because 22 = 4 is one of its divisors.


Write a program that outputs whether the product of two numbers is a square-free number.




The first line contains T (1 ≤ T ≤ 100), the number of test cases. T lines follow, one per test case. Each of these lines contain two integers a and b (1 ≤ a, b ≤ 1018). a and b are NOT necessarily square-free.




Per test case:


  • Output a single line containing "YES" if the product of a and b is square-free, or "NO" otherwise. In any case, do not include quotes in your output.


Sample cases




1 1

6 13

10 2

12 1






hide comments
excel_blaze: 2018-05-19 14:44:10

please please someone help me with this problem
i have used pollard rho +gcd+miller rabin
and still getting tle around 3rd test case

julkas: 2018-05-13 14:07:02

Excelent problem.

Alexey Malistov: 2016-10-15 21:59:21

I believe that some tests are wrong. There is a pair "a" and "b" (I know this pair) where my accepted (by SPOJ) code prints wrong result. But if I correct my code then SPOJ does not accept it.

Sergio Vieri: 2015-10-21 15:10:51

AC 0.46s 2.9M using Assembly... (806 lines, 12758bytes)

Last edit: 2015-10-21 15:14:21
Min_25: 2015-10-18 05:06:17

Incorrect constraints: a or b can be larger than 10^18.

Last edit: 2015-10-18 05:39:40

Added by:kojak_
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:PUCMM Team Selection Contest #4