Siehe Buch "Algorithmen und Problemlösungen mit C++", 2006, Seite 108

1.

/**
 * 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;
}


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.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;
}

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.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;
}

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: 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;
}

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.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;
}