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
~!(*(@*!@^&:
2010-04-10 00:31:13
Text is too small. |
|
Paranoid Android:
2010-02-13 18:27:44
Using gets to take input gives WA. Use scanf. |
|
Frank Rafael Arteaga:
2010-02-09 23:08:28
[Trichromatic] XilinX, I don't know your e-mail.
|
|
[Rampage] Blue.Mary:
2010-02-09 03:38:51
Er, you may e-mail me your data generator and set me as co-author of this problem, I can help you upload data :) |
|
Frank Rafael Arteaga:
2010-02-08 19:03:05
I understand yuor argument. I dont like very strict time too, but I do not have enough internet to upload large files. I tried my code in Python and gives in 0.25s. Clear the brute force algorithm will not at this time even in C++. |
|
Jorge Bernadas:
2010-02-08 04:57:26
Generally here, problems with Time Limits lower than 1s are not seen with good eyes. The 0.3s might be too harsh for most languages. |
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 |