HS10SQFT - Almost square factorisation
For a given number n give all almost square factorisations of n,
so where n=(a^2-1)*(b^2-1) and 1<a<=b.
Input
The first line contains the number of test cases T, where T<=1000. Each of the following T lines contains one integer 0<n<2^62.
Output
For each test case print the case number then on a new line the factorisations in increasing order of a value. If there is no such factorisation then print an error message, see the sample input/output for the correct format!
Example
Input:
4
546939993600
100
172569415200
3467754019458593280
Output:
Case #1:
546939993600=(31^2-1)*(23869^2-1)=(34^2-1)*(21761^2-1)[do not break the line here]
=(271^2-1)*(2729^2-1)=(351^2-1)*(2107^2-1)=(701^2-1)*(1055^2-1)
Case #2:
For n=100 there is no almost square factorisation.
Case #3:
172569415200=(456^2-1)*(911^2-1)
Case #4:
3467754019458593280=(20513^2-1)*(90781^2-1)
hide comments
malioboro:
2016-04-21 14:48:14
I have an accepted solution, but when I try with input : 403560,
|
|
Ashish Lavania:
2012-12-26 10:01:57
30 lines of simple C++ code is more than enough |
Added by: | Robert Gerbicz |
Date: | 2010-11-25 |
Time limit: | 1s |
Source limit: | 4000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: GAWK ICK NODEJS SED |
Resource: | High School Programming League 2010/2011 |