1. 

package acm_107_the_cat_in_the_hat;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_107_the_cat_in_the_hat
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43
*
* @author Martin Lambeck
* @version 1.0, 10.08.2010
*
* Method : math
* Status : Accepted
* Runtime: 2.380
*/

import java.util.Scanner;

public class Main
{
static final double EPSILON = 0.000001;
static int tallest, workers, n;
static Scanner sc = new Scanner(System.in);

public static void main(String[] args)
{
while (testcase());
}

public static boolean testcase()
{
tallest = sc.nextInt();
workers = sc.nextInt();

if (tallest == 0 && workers == 0)
return false;

calcN();

int lazy = 0;
int stack = tallest;
int h = tallest;
int c = 1;

while (h > 1)
{
lazy += c;

c *= n;
h = (int) (h / (1.0+n) + EPSILON);
stack += h * c;
}

System.out.printf("%d %d%n", lazy, stack);

return true;
}

// find k, n such that:
// tallest = (n+1)^k
// &&
// workers = n^k
//
// k = number of "levels" of cats - 1 = number of cats of different size - 1
// n = number of cats in each hat
public static void calcN()
{
double m1 = -1;
double m2 = -1;

for (int k = 2; k <= 31; k++)
{
m1 = Math.pow(tallest, 1.0 / k); //m1 = k-th root of tallest
//m2 = Math.pow(workers, 1.0 / k);

if (Math.abs(m1 - Math.round(m1)) < EPSILON) //if m1 integral number
{
m2 = Math.pow(workers, 1.0 / k); //m2 = k-th root of workers

if (Math.abs(m1 - m2 - 1) < EPSILON) //both conditions met
{
n = (int) (m2 + EPSILON);
return;
}
}
}

n = tallest-1;
}

}


2.



/**

 * ACM Training, SS09

 * ACM Problem #107 The
Cat in the Hat


 * Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43


 *

 * @author Doina Logofatu

 * @version 1.0, 25/09/2009

 *

 * Methode: Math

 * Status : Accepted

 * Runtime: 0.200

 */



#include <iostream>

#include <vector>



using namespace std;



long int gCD(long int a, long
int b){


  long int r;

  while(b!=0){

    r=a%b;

    a=b;

    b=r;

  }

  return a;

}



long int pow(long int b, long
int e){


  long int res = 1;

  while(e){

    if(e%2) res
*= b;


    e /= 2;

    b *= b;

  }

  return res;

}



long int giveP(long int n, long
int &t){


  long int p, i = 2,
k=0; 


  std::vector<int>
a, b;


  while(n-1 &&
i<=n){


    p=0;

    if(n%i==0){

     
b.push_back(i);


     
while(n%i==0 && n-1){p++; n/=i;}


     
a.push_back(p);


    }

    i++;

  }

  long int g = a[0];

  t = 1;

  for(i=1;
i<(int)a.size(); i++) g = gCD(g, a[i]);


  for(i=0;
i<(int)a.size(); i++) t*=pow(b[i], a[i]/g);   


  return g;

}



int main(){

  long int H, W, p1, p2,
k1, k2, nr, p;


 
while(cin>>H>>W && (H||W)){


    if(1==W)
{   


      
p1 = 0;


   
    nr = H;


   
    while(H>1){p1++; H/=2; nr +=H;}


   
    cout << p1 << " " << nr <<
std::endl;


      


    }

    else

     
if(1==H-W)       


       
cout << "1 " << H+W << std::endl;


     
else{       


       
p1 = giveP(H, k1);


       
p2 = giveP(W, k2);


       
if(p1 && p2 && p1-p2)
{                 


         
p = gCD(p1, p2);


         
if(p1>p){


           
k1=pow(k1, p1/p);


           
p1=p;


         
}


         
if(p2>p){


           
k2=pow(k2, p2/p);


           
p2=p;


         
}       


       
}


       
if(p1-p2 || k1-k2-1 != 0)


         
cout << "Es gibt keine Loesung.\n";


       
else{              


         
nr = (pow(k2, p1)-1)/(k2-1);


         
cout << nr << " ";


         
nr = H*k1-H/pow(k1, p1)*pow(k2, p1+1);   
     


         
cout << nr << std::endl;


       
}


      }

    }

  return 0;

}





3.



/**

 * ACM Training, SS09

 * ACM Problem #107 The
Cat in the Hat


 * Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43


 *

 * @author Doina Logofatu

 * @version 1.0, 25/09/2009

 *

 * Methode: Math

 * Status : Accepted

 * Runtime: 0.184

 */



#include <iostream>

#include <vector>

#include <cmath>



using namespace std;



long int gCD(long int a, long
int b){


  long int r;

  while(b!=0){

    r=a%b;

    a=b;

    b=r;

  }

  return a;

}



long int giveP(long int n, long
int &t){


  long int p, i = 2,
k=0; 


  std::vector<int>
a, b;


  while(n-1 &&
i<=n){


    p=0;

    if(n%i==0){

     
b.push_back(i);


     
while(n%i==0 && n-1){p++; n/=i;}


     
a.push_back(p);


    }

    i++;

  }

  long int g = a[0];

  t = 1;

  for(i=1;
i<(int)a.size(); i++) g = gCD(g, a[i]);


  for(i=0;
i<(int)a.size(); i++) t*=(long int)pow((double)b[i],
(double)(a[i]/g));   


  return g;

}



int main(){

  long int H, W, p1, p2,
k1, k2, nr, p;


 
while(cin>>H>>W && (H||W)){


    if(1==W)
{   


      
p1 = 0;


   
    nr = H;


   
    while(H>1){p1++; H/=2; nr +=H;}


   
    cout << p1 << " " << nr <<
std::endl;


      


    }

    else

     
if(1==H-W)       


       
cout << "1 " << H+W << std::endl;


     
else{       


       
p1 = giveP(H, k1);


       
p2 = giveP(W, k2);


       
if(p1 && p2 && p1-p2)
{                 


         
p = gCD(p1, p2);


         
if(p1>p){


           
k1=(long int)pow((double)k1, (double)(p1/p));


           
p1=p;


         
}


         
if(p2>p){


           
k2=(long int)pow((double)k2, (double)(p2/p));


           
p2=p;


         
}       


       
}


       
if(p1-p2 || k1-k2-1 != 0)


         
cout << "Es gibt keine Loesung.\n";


       
else{              


         
nr = ((long int)pow((double)k2, (double)p1)-1)/(k2-1);


         
cout << nr << " ";


         
nr = H*k1-H/((long int)pow((double)k1, (double)p1))*pow((double)k2,
(double)p1+1);         


         
cout << nr << std::endl;


       
}


      }

    }

  return 0;

}



4.



/**

 * ACM Training, SS09

 * ACM Problem #107 The
Cat in the Hat


 * Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43


 *

 * @author Doina Logofatu

 * @version 1.0, 25/09/2009

 *

 * Methode: Math

 * Status : Accepted

 * Runtime: 0.864

 */



#include <iostream>

#include <cmath>



using namespace std;



long int pow(long int b, long
int e){


  long int res = 1;

  while(e){

    if(e%2) res
*= b;


    e /= 2;

    b *= b;

  }

  return res;

}



int main(){

  long int H, W, p, nr;

 
while(cin>>H>>W && (H||W)){


    if(1==W)
{   


   
    p = 0;


   
    nr = H;


   
    while(H>1){p++; H/=2; nr +=H;}


   
    cout << p << " " << nr <<
std::endl;      


    }

    else

     
if(1==H-W)       


       
cout << "1 " << H+W << std::endl;


     
else{       


             
bool flag=false;


   
          long int p, np=1;


   
          for(long int N=2;
N*N<=W; N++){


   
             
p=(long int)(log((double)W)/log((double)N)+10e-6);


   
             
if(pow(N, p)==W && pow(N+1, p)==H){


   
       
        cout << (pow(N,
p)-1)/(N-1) << " " << H*(N+1)-H/pow(N+1, p)*pow(N, p+1)
<< std::endl;


   
       
        flag=true;


   
              }


   
          }


   
          if(!flag)
cout<<"Es gibt keine Loesung.\n";


   
    }


    }

  return 0;

}



5.



/**

 * ACM Training, SS09

 * ACM Problem #107 The
Cat in the Hat


 * Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43


 *

 * @author Doina Logofatu

 * @version 1.0, 25/09/2009

 *

 * Methode: Math

 * Status : Accepted

 * Runtime: 1.012

 */



#include <iostream>

#include <cmath>



int main(){

  long int H, W, p, nr;

  while(std::cin>>H>>W && (H||W)){

    if(1==W) {   

        p = 0;

        nr = H;

        while(H>1){p++; H/=2; nr +=H;}

        std::cout << p
<< " " << nr <<
std::endl;      

    }

    else

     
if(1==H-W)       

        std::cout << "1 "
<< H+W << std::endl;

      else{   
   

             
bool flag=false;

             
long int p, np=1;

             
for(long int N=2; N*N<=W; N++){

                 
p=(long int)(log((double)W)/log((double)N)+10e-6);

                 
if((long int)pow((double)N, p)==W && (long int)pow((double)N+1,
p)==H){

                   
std::cout << (long int)((pow((double)N, p)-1)/(N-1))

                        
<< " " << H*(N+1)-(long int)(H/pow((double)N+1, p))*(long
int)pow((double)N, p+1)

                        
<< std::endl;

                   
flag=true;

                 
}

             
}

             
if(!flag) std::cout<<"Es gibt keine Loesung.\n";

        }

    }

  return 0;

}



6.



/**

 * ACM Training, SS09

 * ACM Problem #107 The
Cat in the Hat


 * Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43


 *

 * @author Doina Logofatu

 * @version 1.0, 25/09/2009

 *

 * Methode: Math

 * Status : Accepted

 * Runtime: 1.000

 */



#include <iostream>

#include <cmath>



int main(){

  long int H, W, p;

  while(std::cin>>H>>W && (H||W)){

    if(1==W) {   

    p = (long int)(log((double)H)/log(2.)+10e-5);
    if((long int)pow(2.0, p)==H) {
      std::cout << p << " " << 2*H-1 <<  std::endl;
    } else {
      std::cout<<"Es gibt keine Loesung.\n";
    }
    }
    else
      if(1==H-W)       
        std::cout << "1 " << H+W << std::endl;
      else{       
              bool flag=false;
              long int p, np=1;
              for(long int N=2; N*N<=W; N++){
                  p=(long int)(log((double)W)/log((double)N)+10e-6);
                  if((long int)pow((double)N, p)==W && (long int)pow((double)N+1, p)==H){
                    std::cout << (long int)((pow((double)N, p)-1)/(N-1))
                         << " " << H*(N+1)-(long int)(H/pow((double)N+1, p))*(long int)pow((double)N, p+1)
                         << std::endl;
                    flag=true;
                  }
              }
              if(!flag) std::cout<<"Es gibt keine Loesung.\n";
        }
    }
  return 0;
}