2013
11-11

Boastin’ Red Socks

You have a drawer that is full of two kinds of socks: red and black. You know that there are at least 2 socks, and not more than 50000. However, you do not know how many there actually are, nor do you know how many are red, or how many are black. (Your mother does the laundry!)

You have noticed, though, that when you reach into the drawer each morning and choose two socks to wear (in pitch darkness, so you cannot distinguish red from black), the probability that you pick two red socks is exactly p/q, where 0 < q and 0 <= p <= q.

From this, can you determine how many socks of each colour are in your drawer? There may be multiple solutions – if so, pick the solution with the fewest total number of socks.

Input consists of multiple problems, each on a separate line. Each problem consists of the integers p and q separated by a single space. Note that p and q will both fit into an unsigned long integer.

Input is terminated by a line consisting of two zeroes.

For each problem, output a single line consisting of the number of red socks and the number of black socks in your drawer, separated by one space. If there is no solution to the problem, print “impossible”.

1 2
6 8
12 2499550020
56 789
0 0


3 1
7 1
4 49992
impossible


//* @author:
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
static public void main( String [] string ) throws Exception{
Scanner cin = new Scanner( System.in );
long p, q;
while( true ) {
p = cin.nextLong();
q = cin.nextLong();
if( p == 0 && q == 0 )
break;
if( p == 0 ) {
System.out.println( "0 2" );
continue;
}
long s, i, j, sum=2;
boolean key = false;
for( i=1; i<=50000 && !key; i++ ) {
if( sum*q%p == 0 ){
s = sum*q/p;
j = (long)Math.sqrt( s );
if( j+1 > 50000 )
break;
if( j*(j+1) == s ) {
System.out.println( (i+1) + " " + (j-i) );
key = true;
break;
}
}
sum += 2*i+2;
}
if( !key )
System.out.println( "impossible" );
}
return;
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧