import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Do it Wrong, Get it Right * * @author vanb */ public class doitwrong { public Scanner sc; public PrintStream ps; /** * A fraction, numerator/denominator */ public class Fraction implements Comparable { /** * Numerator and Denominator need to be longs */ public long numerator, denominator; /** * Create a Fraction * * @param n Numerator * @param d Denominator */ public Fraction( long n, long d ) { numerator = n; denominator = d; } /** * Print the fraction as numerator/denominator * @return A pretty string */ public String toString() { return "" + numerator + "/" + denominator; } /** * Compare this Fraction to another * * @param f Fraction to compare to this one * @return -1 if thisf, 0 if this==f */ public int compareTo( Fraction f ) { long diff = numerator*f.denominator - f.numerator*denominator; if( diff==0 ) diff = numerator - f.numerator; return diff<0 ? -1 : diff>0 ? 1 : 0; } } // Have we seen this fraction before? public HashSet seen = new HashSet(); // Keep a list of unique fraction answers public LinkedList fractions = new LinkedList(); // The inputs public int b, n; /** * Greatest Common Divisor, by Euler's method. * * @param a An integer * @param b Another integer * @return The Greatest Common Divisor of a and b */ public long gcd( long a, long b ) { return b==0 ? a : gcd( b, a%b ); } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "doitwrong.in" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "doitwrong.out" ) ); for(;;) { b = sc.nextInt(); n = sc.nextInt(); if( b==0 && n==0 ) break; // Clear these structures rather than recreate them every time fractions.clear(); seen.clear(); // So, we want to find a and m such that a/m - b/n = (a-b)/(m-n), and 0<=a,m // // Do some algebra on the above equation, and you can come up with this: // (m-n)*(an-bm) = nm(a-b) // anm - an^2 - bm^2 + bnm = anm - bnm // an^2 = 2bmn - bm^2 // a = (2bmn - bm^2)/n^2 // // Now, let m=kn for some k // a = [2(bkn)n - b(kn)^2]/n^2 // a = [bk^2n^2 - 2bkn^2]/n^2 // a = 2bk - bk^2 // // The problem is that k doesn't have to be an integer. But, we can limit it. // k has to be a rational number - that is, a fraction. // Let's look at k's numerator, and denominator. // // Since m=kn and m is an integer, then k's denominator must be a factor of n. // Loop through all possible denominators for k. // We can speed things up by only looping the factor up to sqrt(n), // and handling both factor and n/factor at the same time. for( long factor=1; factor*factor<=n; ++factor ) if( n%factor==0 ) { seekAnswers( factor ); seekAnswers( n/factor ); } // Sort'em and print'em boolean first = true; Collections.sort( fractions ); for( Fraction fraction : fractions ) { ps.print( (first ? "" : " " ) + fraction ); first=false; } ps.println(); } } /** * Seek all answers for a particular denominator of k * * @param kd Denominator of k */ public void seekAnswers( long kd ) { // Now, look at a = 2bk - bk^2. That's a quadratic in k, with roots at 0 and 2 // When k=0, obviously a=0. When k=2, a = 4b-4b = 0. when k=1, a = 2b-b = b. // So, since a must be positive, 0<=k<=2. That means that k's numerator (kn) must // be between 0 and 2*denominator (kd). We'll eliminate 0 (that just gives a=m=0, // and 0/0 is just plain wrong). Still, we need to find another way to limit kn, // because looping from 1 to 2kd can still be too much. // // To simplify the formulas in this next part, I'll use n for kn and d for kd. // I know that n is overused - hopefully, it won't be too confusing. // OK, k=n/d // // Take a closer look at a = 2bk - bk^2. // Let g=GCD(b,d). Then b=gx for some integer x, d=gf for some integer f, and // GCD(x,f)=1 (x and f are mutually prime). // // a = 2bk-bkk // = 2gxn/d - gxnn/dd // = 2gxn/gf - gxnn/ggff // = 2xn/f - xnn/gff // = 2xgfn/gff - xnn/gff // = xn*(2gf-n)/gff // // for a to be an integer, xn*(2gf-n) must be divisible by gff. // In particular, xn*(2gf-n) must be divisible by ff, and since // x and f are mutually prime, then n*(2gf-n) must be divisible by ff. // This forces n to be divisible by f. // That means that 2xn/f is an integer, which means that 2bk is an integer. // // OK, we know that 2bk has to be an integer. // So, that means that 2b*kn/kd has to be an integer. // Now, any common divisor of 2b and kd won't be a problem. // If there are any other divisors of kd, then kn has to cover them. // We can find other divisors of kd by dividing out GCD(2b,kd). // So, kn must be a multiple of kd/GCD(2b,kd). long increment = kd / gcd( b+b, kd ); // Loop through all possible numerators for k. for( long kn=increment; kn<=kd+kd; kn += increment ) { // Is a an integer? Are both terms of a integers? // We know the first term (2bk) is an integer - that's how we chose the increment. // So, test the second term (b*k^2) if( (b*kn*kn)%(kd*kd)==0 ) { // Here's a and m long m = n*kn/kd; long a = (b+b)*kn/kd - b*kn*kn/kd/kd; // Make sure we're not just duplicating b/n if( m!=n && a!=b ) { String id = "" + a + "/" + m; // Make sure we haven't seen this fraction before if( !seen.contains( id )) { Fraction fraction = new Fraction( a, m ); seen.add( id ); fractions.add( fraction ); } } } } } /** * @param args */ public static void main( String[] args ) throws Exception { new doitwrong().doit(); } }