GCDSQF - Another GCD problem
A number is square-free if its prime decomposition contains no repeated factors. For example: 1001 = 7 * 11 * 13 is square-free, but 20 = 2 * 2 * 5 is not square-free.
Square-free numbers can encoding as binary numbers. Here are examples to illustrate:
Sequence of prime numbers 2 3 5 7 11 13 17 ...
- 42 = 2 * 3 * 7 <=> 1101
- 1001 = 7 * 11 * 13 <=> 000111
- 10 = 2 * 5 <=> 101
Your task is given two square-free integers A and B in binary representation compute gcd (A + B, lcm (A, B)). If the result is a square-free number your answer should have the binary format, if the answer is 1 print "relatively prime", and if is neither of these two cases print the result in base 10.
Input
In the first line an integer T (1 <= T <= 100) the number of test cases. The following 2 * T lines will appear integers A and B. The length of the integers A and B encoded in binary form must not exceed 1000 characters.
Output
For each of the T pairs A, B print in the specified format gcd (A + B, lcm (A, B)).
Example
Input: 2 000111 101 11 011 Output: relatively prime 01
Note: In the input may have unnecessary zeros on the right of the numbers A and B, but Your answer only must be with necessary zeros.
hide comments
David:
2021-08-26 23:47:04
Interest problem. Only Java solution to date! |
|
darryl:
2016-08-09 05:03:52
unnecessary zeros cost me 1 WA |
|
surayans tiwari(http://bit.ly/1EPzcpv):
2016-06-07 12:46:01
5600 bytes c++, AC |
|
SRC:
2015-06-17 18:08:09
This is strange, no need to worry about the decimal output ! |
|
NISHANT RAJ:
2014-03-14 16:50:18
who knows printing relative instead of relatively will cost 3 WA. BTW nice problem . |
|
Hasil Sharma:
2014-01-09 12:35:34
good one :) |
|
Akshat Jain:
2013-12-27 18:04:02
NO need of chekin for decimal output ....AC Last edit: 2013-12-28 11:08:38 |
|
saket diwakar:
2013-01-28 17:52:51
loved doing this one...:) |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-12-24 10:17:00
enjoyed solving this problem... 284B in C ;-) |
|
V Sriharsha:
2012-07-16 14:25:03
so easy and still 0.5 points |
Added by: | Frank Rafael Arteaga |
Date: | 2010-02-07 |
Time limit: | 0.100s |
Source limit: | 6000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | own problem, Discrete Math |