1.

/* Problemnr: 10722 Super Lucky Numbers
 * Sprache: Java
 * Autor : Peter Schnitzler
 * Status : AC
 * Zeit : 1.936
 */


import java.math.BigInteger;
import java.util.Scanner;


public class Main
{

    private static BigInteger noOne[][] = new BigInteger [100][125];
    private static BigInteger allNums[][] = new BigInteger [100][125];
    
    
    private static BigInteger getNum(int base, int digits)
    {
        digits--;
        
        if (allNums[digits][base - 4] == null)
        {
            if (digits == 0)
            {
                allNums[0][base - 4] = BigInteger.valueOf(base - 1);
                //everything but zero
            }
            else
            {
                BigInteger temp = getNum(base, digits).multiply(BigInteger.valueOf(base - 1));
                //everything but three
                
                temp = temp.add(getNoOne(base, digits));
                //the three
                
                allNums[digits][base - 4] = temp;
            }
        }
        
        return allNums[digits][base - 4];
    }
    
    
    private static BigInteger getNoOne(int base, int digits)
    {
        digits--;
        
        if (noOne[digits][base - 4] == null)
        {
            if (digits == 0)
            {
                noOne[0][base - 4] = BigInteger.valueOf(base - 2);
                //everything but zero or one
            }
            else
            {
                BigInteger temp = getNum(base, digits).multiply(BigInteger.valueOf(base - 2));
                //everything but three or one
                
                temp = temp.add(getNoOne(base, digits));
                //the three
                
                noOne[digits][base - 4] = temp;
            }
        }
        
        return noOne[digits][base - 4];
    }


    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        
        int base, digits;
        
        base = scan.nextInt();
        digits = scan.nextInt();
        
        while (base != 0)
        {
            System.out.println(getNum(base, digits).toString());
            
            base = scan.nextInt();
            digits = scan.nextInt();
        }
    }
}

2. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10722 Superlucky Numbers
*
* @author Julius Tschannerl
* @author David Leib
* @version 1.0, 05/25/2009
*
* Status : Accepted
* Runtime: 1.488
*/


import java.util.*;
import java.math.*;

public class Main {


public static void main(String[] args) {


Scanner sc = new Scanner(System.in);
int b,n;
b = sc.nextInt(); //basis
n = sc.nextInt(); //Stellenzahl

BigInteger[] l = new BigInteger[200];

while(b != 0 && n != 0){
if(n<= 0)
System.out.println("0");
if(n==1)
System.out.println(b-1);
else{
BigInteger B = new BigInteger(b+"");
l[1] = B;

//Berechnung aller möglichen 2 stelligen Zahlen zur basis B: B2
l[2] = B.pow(2);

//bei zweistelligen eine 13 möglich: B2-1
l[2] = l[2].subtract(new BigInteger(1+""));

//um 2-stelligen Zahlen mit f¼hrenden Nullen loszuwerden, muss die Basis abgezogen werden
//daraus kann man alle 3-stelligen Zahlen ohne 13 ausrechnen.
//man nimmt das ergebnis f¼r die 2-stelligen, multipliziert es mit der Basis, f¼r die zus¤tzliche stelle.
//dann subtrahiert man alle möglichkeiten f¼r 2-stellige Zahlen mit f¼hrenden nullen aber ohne 13 (den man zwei schritte davor abgetogen hat)
//um 3-stellige mit f¼hrenden nullen auszuschlie�en.
//2-stellige mit f¼hrenden nullen werden mit abgezogen, da damit die 1 ausgeschlossen wird, die eine zus¤tzliche 13 verursachen könnte:
//daraus ergibt sich eine rekursive formel: F_n = F_n-1 - F_n-2
//das wird soooft wiederholt, bis die Stellenanzahl des inputs erreicht wird.
for(int i = 3; i<=n;i++){
l[i] = l[i-1].multiply(B);
l[i] = l[i].subtract(l[i-2]);
}

//vor Ausgabe noch rekursionssubtraktion ausf¼hren.
System.out.println(l[n].subtract(l[n-1]));
}
b = sc.nextInt();
n = sc.nextInt();
}
}

}


3.

/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10722 (Super Lucky Numbers)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1663
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 05/29/2009
*
* Status : Accepted
* Runtime: 1.248
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.TreeMap;
import java.util.StringTokenizer;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

// StringBuilder fr die Ausgabe
StringBuilder output = new StringBuilder();

StringTokenizer token;
// Basis
int b;
// Anzahl der Stellen
int n;

Main lucky = new Main();

// Cache zum speichern bereits berechneter Werte
lucky.cache = new TreeMap<Integer, BigInteger>();

while(true){

// Die beiden Werte auslesen
token = new StringTokenizer(reader.readLine());
b = Integer.parseInt(token.nextToken());
n = Integer.parseInt(token.nextToken());

// Abberechen wenn beide Werte 0 sind
if(n==0 && b==0)break;

// Cache leeren
lucky.cache.clear();
// Anzahl an die Ausgabe anhngen
output.append(lucky.luckyNumbers(b, n));
output.append("\n");

}
System.out.print(output);
}

// Cache fr bereits berechnete Werte
TreeMap<Integer, BigInteger> cache;

/* Anzahl der SuperLuckyNumbers rekursiv berechnen.
*
*/
BigInteger luckyNumbers(int b, int n){

if(n==1){
return BigInteger.valueOf(b-1);
}

if(n==2){
return BigInteger.valueOf(b*b-b-1);
}

// Prfen ob der Wert bereits berechnet wurde
if(cache.containsKey(n))return cache.get(n);

// Berechnen und im cache speichern
BigInteger result = BigInteger.valueOf(b).multiply(luckyNumbers(b, n-1)).subtract(luckyNumbers(b, n-2));

cache.put(n, result);

return result;
}
}



4.



/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem: Super Lucky Numbers (10722)
* @author Christian Mitterreiter
* @author Rolf Luigs
* @version 1.0, 06/07/2009
* Status : Accepted
* Runtime: 2.412
*/


import java.math.BigInteger;
import java.util.HashMap;
import java.util.Scanner;


public class Main {


static HashMap<BigInteger, BigInteger> res = new HashMap<BigInteger, BigInteger>(); //Map fr Ergebnisse

public static BigInteger calc(BigInteger b, BigInteger n) {
BigInteger zwei = new BigInteger("2");
BigInteger ergebnis;

if (n.equals(BigInteger.ONE)) return (b.subtract(BigInteger.ONE));
if (n.equals(zwei)) return (b.pow(2).subtract(b).subtract(BigInteger.ONE));

if(res.containsKey(n)) return res.get(n); //wenn Zahl schon in der Map ist, rckgabe der Zahl, andernfalls berechnen

ergebnis = (b.multiply(calc(b, n.subtract(BigInteger.ONE))).subtract(calc(b, n.subtract(zwei))));

res.put(n, ergebnis); //abspeichern der berechneten Zahl
return ergebnis;
}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

BigInteger b = sc.nextBigInteger(); //einlesen der Zahlen
BigInteger n = sc.nextBigInteger();

while(!b.equals(BigInteger.ZERO) || !n.equals(BigInteger.ZERO)) {

System.out.printf("%d%n",calc(b, n)); //Ausgabe
res.clear(); //zurcksetzen der Map

b = sc.nextBigInteger();
n = sc.nextBigInteger();
}
}
}

5. 

/*

 * ACM Programming Contest

 * Problem: 10722 (Super Lucky Numbers)

 * Status: Accepted

 * Language: Java

 * Runtime: 1.416

 * Date: 2009-06-03 12:26:02

 * Author: Andreas Kunft

 */

import java.math.BigInteger;

import java.util.Scanner;



public class Main {



    public static void main(String... args) {

        Scanner s = new Scanner(System.in);

        int b, n;

        while (s.hasNext()) {

            b = s.nextInt();

            n = s.nextInt();

            if (b == 0 && n == 0)

                break;



            long l1 = b - 1;

            if (n == 1) {

                System.out.println(l1);

                continue;

            }

            long l2= b * b - b - 1;

            if (n == 2) {

                System.out.println(l2);

                continue;

            }



            BigInteger l_1 = new BigInteger(String.valueOf(l1));

            BigInteger l_2 = new BigInteger(String.valueOf(l2));

            BigInteger b_ = new BigInteger(String.valueOf(b));



            BigInteger out = new BigInteger("1");

            for (int i = 2; i < n; i++) {

                out = b_.multiply(l_2).subtract(l_1);

                l_1 = l_2;

                l_2 = out;

            }



            System.out.println(out.toString().length());

        }

    }

}


6.

/*
* ACM Programming Contest
*
* Problem: 10722 - Super Lucky Numbers
* Status: Accepted
* Language: C
* Runtime: 1.564
* Date: 2009-06-04 09:08:37
* Author: Axel Fiedler
*
*/

/* BigInt Funktionen von http://www.geocities.com/acmbeganer/bignum.htm */
/* Knnte schneller sein, wenn nur Zahlen >= 0 bercksichtigt werden */
/* und nicht bentigter Code etc. entfernt wird */

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAXDIGITS 212 /* maximum length bignum */
#define PLUS 1 /* positive sign bit */
#define MINUS -1 /* negative sign bit */

#define max(a, b) ((a > b) ? a : b)

typedef struct
{
char digits[MAXDIGITS]; /* represent the number */
int signbit; /* 1 if positive, -1 if negative */
int lastdigit; /* index of high-order digit */
} bignum;

void print_bignum(bignum *n);
void int_to_bignum(int s, bignum *n);
/*void int_to_bignum(char *s, bignum *n);*/
void initialize_bignum(bignum *n);
int add_bignum(bignum *a, bignum *b, bignum *c);
int subtract_bignum(bignum *a, bignum *b, bignum *c);
void zero_justify(bignum *n);
int compare_bignum(bignum *a, bignum *b);
void multiply_bignum(bignum *a, bignum *b, bignum *c);
void copy(bignum *a, bignum *b);
void divide_bignum(bignum *n1, bignum *n2, bignum *n3, bignum *n4);

/* ************************************** */
/* print a Big integer */
/* Input : A big integer pointer */
/* Return : None */
/* ************************************** */
void print_bignum(bignum *n)
{
if (n->signbit == MINUS)
printf("-");

printf("%s\n", n->digits);
}

/* *********************************************** */
/* Convert an integer into big integer */
/* Input : A integer and a big integer */
/* pointer */
/* Return : None */
/* *********************************************** */
void int_to_bignum(int s, bignum *n)
{
if (s >= 0)
n->signbit = PLUS;
else
n->signbit = MINUS;

int t = abs(s);

sprintf(n->digits, "%d", t);
n->lastdigit = strlen(n->digits);
}

/* ************************************************ */
/* Convert an char array into big integer */
/* Input : A string and a big integer */
/* pointer */
/* Return : None */
/* ************************************************ */
/*void int_to_bignum(char *s, bignum *n)
{
int i;

if (s[0] != -1)
{
n->signbit = PLUS;
i = 0;
}
else
{
i = 1;
n->signbit = MINUS;
}

strcpy(n->digits,&s[i]);
n->lastdigit = strlen(n->digits);
}*/

/* **************************************** */
/* Inatilize a zero integer */
/* Input : A big integer pointer */
/* Return : None */
/* **************************************** */
void initialize_bignum(bignum *n)
{
int_to_bignum(0,n);
}

/* *********************************************************** */
/* Add two big integer */
/* Input : Three big integer pointer a,b,c */
/* where a & b is argument of addition */
/* and c is the result. c = a + b */
/* Return : Number of carry */
/* *********************************************************** */
int add_bignum(bignum *a, bignum *b, bignum *c)
{
int carry; /* carry digit */
int i, j , op = 0; /* counter */
int n_carry;

initialize_bignum(c);

if (a->signbit == b->signbit)
c->signbit = a->signbit;
else
{
if (a->signbit == MINUS)
{
a->signbit = PLUS;
n_carry = subtract_bignum(b, a, c);
a->signbit = MINUS;
}
else
{
b->signbit = PLUS;
n_carry = subtract_bignum(a, b, c);
b->signbit = MINUS;
}

return n_carry;
}

if (a->lastdigit < b->lastdigit)
return add_bignum(b, a, c);

int k = c->lastdigit = a->lastdigit + 1;

c->digits[k--]='\0';
carry = 0;
n_carry = 0;

for (i = b->lastdigit - 1, j = a->lastdigit - 1; i >= 0; i--, j--)
{
carry = b->digits[i] - '0' + a->digits[j] - '0' + carry;
c->digits[k--] = (carry%10) + '0';
carry = carry/10;

if(carry)
n_carry++;
}

for (; j >= 0; j--)
{
carry = a->digits[j] - '0' + carry;
c->digits[k--] = (carry%10) + '0';
carry = carry/10;

if(carry)
n_carry++;
}

if (carry)
c->digits[k] = carry + '0';
else
{
char string[MAXDIGITS];
strcpy(string, &c->digits[1]);
strcpy(c->digits, string);
c->lastdigit = c->lastdigit - k - 1;
}

return n_carry;
}

/* ************************************************************ */
/* Subtract two big integer */
/* Input : Three big integer pointer a,b,c */
/* where a & b is argument of subtraction */
/* and c is the result. */
/* Return : Number of borrow */
/* ************************************************************ */
int subtract_bignum(bignum *a, bignum *b, bignum *c)
{
register int i, j, op = 0; /* counter */
int n_borrow;
int temp;

c->signbit = PLUS;

if ((a->signbit == MINUS) || (b->signbit == MINUS))
{
b->signbit = (-1)*b->signbit;
n_borrow = add_bignum(a, b, c);
b->signbit = (-1)*b->signbit;

return n_borrow;
}

if (compare_bignum(a, b) == PLUS)
{
n_borrow = subtract_bignum(b, a, c);
c->signbit = MINUS;

return n_borrow;
}

int k = c->lastdigit = max(a->lastdigit, b->lastdigit);

n_borrow = 0;
c->digits[k--] = '\0';

for (i = a->lastdigit - 1, j = b->lastdigit - 1; j >= 0; i--, j--)
{
temp = a->digits[i] - '0' - (b->digits[j] - '0' + op);

if (temp < 0)
{
temp += 10;
op = 1;
n_borrow++;
}
else
op = 0;

c->digits[k--] = temp + '0';
}

while (op)
{
temp = a->digits[i--] - op - '0';

if(temp < 0)
{
temp += 10;
op = 1;
n_borrow++;
}
else
op = 0;

c->digits[k--] = temp + '0';
}

for (; i >= 0; i--)
c->digits[k--] = a->digits[i];

for (i = 0; !(c->digits[i] - '0'); i++);

c->lastdigit = c->lastdigit - i;

if (i == a->lastdigit)
strcpy(c->digits, "0");
else
{
char string[MAXDIGITS];
strcpy(string, &c->digits[i]);
strcpy(c->digits, string);
}

return n_borrow;
}

/* **************************************************** */
/* Compare two big integer */
/* Input : Two big integer pointer a,b */
/* Return : 0,1 or -1, */
/* 0 for a=b */
/* 1 for a < b */
/* -1 for a>b */
/* **************************************************** */
int compare_bignum(bignum *a, bignum *b)
{
int i; /* counter */

if ((a->signbit == MINUS) && (b->signbit == PLUS))
return PLUS;

if ((a->signbit == PLUS) && (b->signbit == MINUS))
return MINUS;

if (b->lastdigit > a->lastdigit)
return (PLUS*a->signbit);

if (a->lastdigit > b->lastdigit)
return (MINUS*a->signbit);

for (i = 0; i < a->lastdigit; i++)
{
if (a->digits[i] > b->digits[i])
return (MINUS*a->signbit);

if (b->digits[i] > a->digits[i])
return (PLUS*a->signbit);
}

return 0;
}

/* *************************************************************** */
/* Multiply two big integer */
/* Input : Three big integer pointer a,b,c */
/* where a & b is argument of multiplication */
/* and c is the result. */
/* Return : Number of borrow */
/* *************************************************************** */
void multiply_bignum(bignum *a, bignum *b, bignum *c)
{
long int n_d;
register long int i, j, k;
short int num1[MAXDIGITS], num2[MAXDIGITS], of = 0, res[MAXDIGITS] = {0};

n_d = (a->lastdigit < b->lastdigit) ? b->lastdigit : a->lastdigit;
n_d++;

for (i = 0, j = a->lastdigit - 1; i < a->lastdigit; i++, j--)
num1[i] = a->digits[j] - 48;

for (i = 0, j = b->lastdigit - 1; i < b->lastdigit; j--, i++)
num2[i] = b->digits[j] - 48;

res[0] = 0;

for (j = 0; j < b->lastdigit; j++)
{
for (i = 0, k = j; i < a->lastdigit || of; k++, i++)
{
if (i < a->lastdigit)
res[k] += num1[i]*num2[j] + of;
else
res[k] += of;

of = res[k]/10;
res[k] = res[k]%10;
}
}

for (i = k - 1, j = 0; i >= 0; i--, j++)
c->digits[j] = res[i] + 48;

c->digits[j] = '\0';
c->lastdigit = k;
c->signbit = a->signbit*b->signbit;
}

/* ******************************************************* */
/* Copy one big integer into another */
/* Input : Two big integer pointer a,b */
/* where a is destinition & b source */
/* Return : None */
/* ******************************************************* */
void copy(bignum *a, bignum *b)
{
a->lastdigit = b->lastdigit;
a->signbit = b->signbit;
strcpy(a->digits, b->digits);
}

/* **************************************************************** */
/* Divide two big integer */
/* Input : FOur big integer pointer n1,n2,n3,n4 */
/* where n1 & n2 is argument of dividition, */
/* n3 is the result and n4 is module */
/* Return : None */
/* **************************************************************** */
void divide_bignum(bignum *n1, bignum *n2, bignum *n3, bignum *n4)
{
initialize_bignum(n3);

bignum a, b, temp;
a.signbit = b.signbit = temp.signbit = PLUS;
int asign = n1->signbit;
n1->signbit = PLUS;
int bsign = n2->signbit;
n2->signbit = PLUS;
temp.lastdigit = 0;

int_to_bignum(1, &b);
copy(&a, n1);

while (compare_bignum(&a, n2) < 1)
{
subtract_bignum(&a, n2, n4);
add_bignum(n3, &b, &temp);
copy(&a, n4);
copy(n3, &temp);
}

n1->signbit = asign;
n2->signbit = bsign;
n3->signbit = n1->signbit*n2->signbit;

if (n4->digits[0] != '0')
n4->signbit = asign;
}

#define LIMIT 129

bignum L[LIMIT];

int main()
{
int b, n, i;

while (scanf("%d%d", &b, &n) && ((b > 0) && (n > 0)))
{
int_to_bignum((b - 1), &L[0]);
int_to_bignum(((b*b) - b- 1), &L[1]);

for (i = 2; i < n; i++)
{
int_to_bignum(b, &L[i]);
multiply_bignum(&L[i], &L[i - 1], &L[i]);
subtract_bignum(&L[i], &L[i - 2], &L[i]);
}

print_bignum(&L[n - 1]);
}

return 0;
}

7.


/**
* ACM Training, SS09
* ACM Problem #10722 Super Lucky Numbers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2177
*
* @author Doina Logofatu
* @version 1.0, 18/09/2009
*
* Methode: DP / Math
* Status : Accepted
* Runtime: 1.252
*/

import java.io.*;
import java.math.*;
import java.util.*;


public class Main {


public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);

while (true) {
if (!sc.hasNextInt()) {
break;
}
int b = sc.nextInt();
if (!sc.hasNextInt()) {
break;
}
int n = sc.nextInt();
if (n == 1) {
System.out.println(b - 1);
continue;
}
if(b==0 && n==0) {
break;
}
BigInteger l2 = BigInteger.valueOf(b * b - b - 1);
BigInteger l1 = BigInteger.valueOf(b-1);

for (int i = 3; i <= n; i++) {
BigInteger l3 = BigInteger.valueOf(b).multiply(l2);
l3 = l3.subtract(l1);
l1 = l2;
l2 = l3;
}

pw.println(l2);
pw.flush();
}
pw.flush();
}

}