1.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

/**
* Angewandte Mathematik, SS11
* Problem: 10139 Factorvisors
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1080
*
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 06/04/2011
*
* Method : Primfaktorzerlegung, schnelle Berechnung der Primfaktoren in einer Fakult¦t
* Status : Accepted
* Runtime: 1.052
*/

public class Main
{

static BitSet noPrimes;

public static void main(String[] args) throws IOException
{
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer;
int number;
int fak;
String line;
while((line = buffer.readLine()) != null)
{
tokenizer = new StringTokenizer(line);
fak = new Integer(tokenizer.nextToken());
number = new Integer(tokenizer.nextToken());

if((fak==0 && number==1) || (number!=0 && fak!=0 && isFakDivByN(fak, number)))
{
System.out.println(number+" divides "+fak+"!");
}
else
{
System.out.println(number+" does not divide "+fak+"!");
}
}
}

/**
* Gibt an wie oft ein Faktor n in einer Fakult¦t fak vorkommt
* @param fak Fakult¦t
* @param n Faktor
* @return H¦ufigkeit des Faktors
*/
public static int getPowerInFak(int fak, int n)
{
int power = 0;
for (int div = n; n <= div ; div *= n)
{
power += fak/div;
}
return power;
}

/**
* Gibt zur¾ck ob nÊ| fak!
* @param fak Fakult¦t (fak!)
* @param n nat¾rliche Zahl
* @return true wenn die Fakult¦t durch n dividierbar ist, sonst false
*/
public static boolean isFakDivByN(int fak, int n)
{
if(fak>n)
{
return true;
}
else if(fak==n)
{
return true;
}

Map<Integer,Integer> primeFactors = getPrimeFactors(n);
List<Integer> factors = new ArrayList<Integer>(primeFactors.keySet());

for(int i = 0; i < factors.size(); i++)
{
int prime = factors.get(i);
if(primeFactors.get(prime) > getPowerInFak(fak, prime))
{
return false;
}
}
return true;
}

/**
* Liefert eine HashMap mit key=Primfaktor und value=Anzahl der
* nat¾rlichen Zahl n zur¾ck. D.h. es
* wird die komplette Primfaktorzerlegung durchgef¾hrt
* @param n nat¾rliche Zahl
* @return Primfaktoren mit der Anzahl
*/
public static Map<Integer,Integer> getPrimeFactors(int n)
{
Map<Integer,Integer> map = new HashMap<Integer, Integer>();

while (n % 2 == 0)
{
n /= 2;
map.put(2, map.get(2) == null ? 1 : map.get(2) + 1);
}
int counter = 3;
int tmp = n;

while (counter <= ((double)Math.sqrt(tmp) + 1))
{
if (n % counter == 0)
{
n /= counter;
map.put(counter, map.get(counter) == null ? 1: map.get(counter) + 1);
}
else
{
counter += 2;
}
}
if (n > 1)
{
map.put(n, map.get(n) == null ? 1 : map.get(n) + 1);
}

return map;
}
}

2.

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
* Angewandte Mathematik, SS11
* Problem: 10139 Factovisors
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1080
*
* @author Fabian Trampusch
* @author Robert Schwarz
* @version 4.0, 04/10/2011
* Nachdem Versionen 1-3 alle WA oder TLE waren....
*
* Method : Nachdenken
* Status : Accepted
* Runtime: 1.536
*/

public class Main {
public static void main(String args[]) {
try {
int div, fac;
String[] line;
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));

while (true) {
line = br.readLine().split(" ");

div = Integer.parseInt(line[1]);
fac = Integer.parseInt(line[0]);

if (divides(div, fac)) {
System.out.println(line[1] + " divides " + line[0] + "!");
} else {
System.out.println(line[1] + " does not divide " + line[0]
+ "!");
}
}
} catch (Exception e) {

}
}

private static boolean divides(int div, int fac)
{
//1 teilt alles
if (div == 1)
return true;
//0 teilt nichts
if (div == 0)
return false;
//0! = 1
if (fac == 0)
fac = 1;

//1! / n geht nur wenn n = 1 ist
if (fac == 1 && div != 1)
return false;

//Hoffentlich selbsterklärend
if (div <= fac)
return true;

//Untere Grenze
int sqrtDiv = (int)Math.sqrt(div);

//Wie oft der Primfaktor vorkommt
int p = 0;

//
//Der Trick besteht darin, die Primfaktorzerlegung des Divisors sich anzuschauen.
//Dies muss eine "Teilmenge" der Primfaktorzerlegung der Fakultäten sein.
//Ist nur ein einziger Primfaktor im divisor der nicht in fakultät ist oder ein Primfaktor
//öfters als in der Fakultät enthalten, so teilt der divisors die fakultät nicht.
//

while(div % 2 == 0)
{
div /= 2;
p++;
}

if (p > 0)
{
for (int currentFac = 2; currentFac <= fac && p > 0; currentFac += 2)
{
int currentFacTemp = currentFac;
while (currentFacTemp % 2 == 0 && p > 0)
{
currentFacTemp /= 2;
p--;
}
}

//Primfaktor kam in der Fakultät nicht oft genug vor
if (p > 0)
return false;
}

for (int i = 3; i <= sqrtDiv && div > 1; i += 2)
{
while(div % i == 0)
{
div /= i;
p++;
}

for(int currentFac = i; currentFac <= fac && p > 0; currentFac++)
{
int currentFacTemp = currentFac;
while(currentFacTemp % i == 0 && p > 0)
{
currentFacTemp /= i;
p--;
}
}

if (p > 0)
return false;
}

//div is prime
if (div > 1 && div > fac)
return false;
else
//div teilt fakultät
return true;
}
}

3.

/**
* Angewandte Mathematik, SS11
* Problem: 10139 Factovisors
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1080
*
* @author Markus Schöllner
* @author Andreas Maier
* @version 1.0, 07/04/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.424
*/


import java.util.*;

public class Main {

public static void main(String[] args){
Scanner input = new Scanner(System.in);
int fac,div;
boolean divides;

while(input.hasNextInt()){

fac = input.nextInt();
div = input.nextInt();
divides = true;

if(div == 0) System.out.println(div+" does not divide "+fac+"!");
else {
if(div <= fac) System.out.println(div+" divides "+fac+"!");
else {

Map<Integer, Integer> map = primes(div);
for(int number : map.keySet()) {
if(powerOfPrime(fac, number) < map.get(number)) divides = false;
if(divides == false) break;
}
if(divides) System.out.println(div+" divides "+fac+"!");
else System.out.println(div+" does not divide "+fac+"!");
}
}
}
}

public static long powerOfPrime(long fac, long number)
{
long result = 0;
for (long power = number ; power <= fac ; power = power * number)
result = result + fac/power;
return result;
}


public static Map<Integer, Integer> primes(int div) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

int anzahl = 0;
while (div % 2 == 0) {
anzahl++;
div = div/2;
}
if (anzahl != 0) map.put(2, anzahl);

anzahl = 0;
while (div % 3 == 0) {
anzahl++;
div = div/3;
}
if (anzahl != 0) map.put(3, anzahl);

anzahl = 0;
while (div % 5 == 0) {
anzahl++;
div = div/5;
}
if (anzahl != 0) map.put(5, anzahl);

int prime = 7;
int diffNextPrime = 4;

while (prime * prime <= div) {
anzahl = 0;
if(prime % 5 != 0) {
while (div % prime == 0) {
anzahl++;
div = div/prime;
}
if (anzahl != 0) map.put((int)prime, anzahl);
}
prime = prime + diffNextPrime;
if(diffNextPrime == 2) diffNextPrime = 4;
else diffNextPrime = 2;
}
if (div > 1) map.put(div, 1);
return map;
}

}

4.

/**
 * Angewandte Mathematik, SS11
 * Problem: 10139 Factovisors
 * Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2113
 *
 * @author Westerfield, Christopher
 * @author Gent Selmanaj
 * @author Marco Schuster
 * @version 1.0, 03/21/2011
 *
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 0.140
 */
import java.util.*;
import java.io.*;
class Main
{
public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = reader.readLine();
while (true) {
StringTokenizer tokenizer = new StringTokenizer(line);
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
if (test(n, m))
System.out.println(m + " divides " + n + "!");
else
System.out.println(m + " does not divide " + n + "!");
if (!reader.ready())
break;
line = reader.readLine();
}
}
public static boolean test(int n, int m) {
if (m == 0)
return false;
if (m <= n)
return true;
Map<Integer, Integer> facts = primeFactors(m);
for (int key : facts.keySet()) {
if (getPowers(n, key) < facts.get(key))
return false;
}
return true;
}
public static Map<Integer, Integer> primeFactors(int n) {
Map<Integer, Integer> facts = new HashMap<Integer, Integer>();
int e = 0;
while (n % 2 == 0) {
e++;
n /= 2;
}
if (e != 0)
facts.put(2, e);
e = 0;
while (n % 3 == 0) {
e++;
n /= 3;
}
if (e != 0)
facts.put(3, e);
long t = 5;
int diff = 2;
while (t*t <= n) {
e = 0;
while (n % t == 0) {
e++;
n /= t;
}
if (e != 0)
facts.put((int)t, e);
t += diff;
diff = 6 - diff;
}
if (n > 1)
facts.put(n, 1);
return facts;
}
public static int getPowers(int n, int p) {
int result = 0;
for (long power = p; power <= n; power *= p)
result += n/power;
return result;
}
}
5.

/**

 * Angewandte Mathematik, SS11

 * Problem: 10139 - Factovisors

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

 *

 * @author Schramm Felix

 * @author Vogel Johannes

 * @version 1.0, 04/12/2011

 *

 * Method : Ad-Hoc

 * Status : Accepted

 * Runtime: 1.280

 */





import java.util.Scanner;



public class Main {



    public static void main(String args[]){



        Scanner input = new Scanner(System.in);

        while(input.hasNextInt()){

            boolean divides = true;

            int factorial = input.nextInt();

            int number = input.nextInt();

            if(number==0)

                divides=false;                //null teilt nichts

            int num = number;

            int factor = 2;

            boolean test = true;

            //solange der faktor kleiner als die wurzel des rests ist
und alle vorherighen teiler enthalten waren

            while(test&&divides){

                boolean devidable = true;

                int countInNumber = 0;

                while(devidable)

                    if(num%factor==0){

                        num/=factor;

                        countInNumber++;

                    }else

                        devidable=false;

                int countInFactorial = 0;

                //teiler für alle vielfachen des faktors einmal enthalten

                //teiler für alle vielfachen des quadrats einaml enthalten

                // ...

                for(int
j=1;Math.pow(factor,j)<=factorial&&countInNumber>countInFactorial;j++)

                    countInFactorial+=factorial/Math.pow(factor, j);

                if(countInNumber>countInFactorial)

                    divides=false;

                if(factor==2)

                    factor++;

                else

                    if(factor*factor<num)

                        factor+=2;

                    else

                        test=false;;



            }

            if(num>factorial&&num!=1)

                divides=false;

            if(divides)

                System.out.println(number + " divides " + factorial + "!");

            else

                System.out.println(number + " does not divide " +
factorial + "!");



        }

    }





}

6.

/**

 * Angewandte Mathematik, SS11

 * Problem: 10139 - Factovisors

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

 *

 * @author Schramm Felix

 * @author Vogel Johannes

 * @version 2.0, 04/11/2011

 *

 * Method : Ad-Hoc

 * Status : bestimmt richtig

 * Runtime: leider zu langsam, aber ich habs solange dran geschrieben,
dass ich es trotzdem abgeben muss

 */







import java.util.*;



public class Main {

    public static void main(String args[]){

        Scanner input = new Scanner(System.in);

        while(input.hasNextInt()){

            factors factorial = new factorialFactors(input.nextInt());

            factors number = new numberFactors(input.nextInt());

            if(number.devides(factorial))

                System.out.println(number + " divides " + factorial);

            else

                System.out.println(number + " does not divide " +
factorial);

        }

    }



}



abstract class factors{

    ArrayList<Integer> factorList = new ArrayList<Integer>();

    String toStr = new String();

    static primeFactors primes = new primeFactors();



    boolean devides(factors divident){

        //System.out.println("\n" + factorList + "\n" +
divident.getList() + "\n");

        while(!factorList.isEmpty()){

            int factor = factorList.remove(0);

            if(divident.getList().contains(factor))

                divident.getList().remove((Object)factor);

            else

                return false;

        }

        return true;

    }



    public void factorize(){

        ArrayList<Integer> factorized = new ArrayList<Integer>();

        while(!factorList.isEmpty()){

            factorized.addAll(primes.factorize(factorList.remove(0)));

        }

        factorList=factorized;



    }



    public ArrayList<Integer> getList(){

        return factorList;

    }



    public String toString(){

        return toStr;

    }

}



class numberFactors extends factors{



    numberFactors(int number){

        toStr = "" + number;

        factorList.add(number);

        if(number!=0)

            factorize();

    }



}



class factorialFactors extends factors{



    factorialFactors(int factorial){

        toStr = factorial + "!";

        while(factorial>1)

            factorList.add(factorial--);

        factorize();

    }



}



class primeFactors extends factors{

    int max=2;

    primeFactors(){

        toStr = "all Primes up to " + max;

        factorList.add(2);

    }



    List<Integer> factorize(Integer number){

        ArrayList<Integer> factrz = new ArrayList<Integer>();

        if(number>max)

            extendTo(number);

        int primeToTest = 0;

        while(number!=1){

            int prime = factorList.get(primeToTest);

            if(number%prime==0){

                factrz.add(prime);

                number/=prime;

            }else

                ++primeToTest;



        }



        return factrz;

    }



    private void extendTo(int newMax){

        for(int i=max+1;i<=newMax;i++){

            boolean prime = true;

            int primeToTest = 2;

            int posOfPrime=0;

            while(primeToTest<i/2&&prime){

                primeToTest=factorList.get(posOfPrime++);

                prime=!(i%primeToTest==0);

            }

            if(prime)

                factorList.add(i);
        }

        max=newMax;

    }


}


7.
/**
* Angewandte Mathematik, SS11
* Problem: 10139 - Factovisors
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1080
* @author Sebastian Stumpf
* @author Benjamin Vogt
* @version 1.0, 2011-04-11 20:39:37
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.000
*/

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


public class Main
{
public static boolean dividesFac(int fac, int div)
{
//hier werden die Startwerte 0,1 abgefangen, die ich bei meiner späteren bberechnung nicht brauchen kann
if(div == 0)
return false;
if(div == 1)
return true;
if(fac == 0 || fac == 1)
return false;
//wenn der divisor kleiner gleich fak ist ist fak nat durch div teilbar
if(div <= fac)
return true;
int expDiff = 0;
//der größte Primfaktor von div kann maximal sqrt(div)sein, wenn div sqrt*sqrt ist. alle möglichen faktoren
//werden bei den vorigen schleifendurchläufen aussortiert
int max = (int)Math.sqrt(div);
//Exponenten von Primfaktor 2 vergleichen:
while(div % 2 == 0)
{
expDiff++;
div /= 2;
}
for(int i = 2; expDiff != 0 && i <= fac; i++)
{
int temp = i;
while(expDiff != 0 && temp % 2 == 0)
{
expDiff--;
temp /= 2;
}
}
if(expDiff > 0)
return false;
//Exponenten der restlichen Primfaktoren vergleichen
for(int i = 3; i <= max; i += 2)
{
//expDiff steht für die Differenz zwischen den exponenten der primfaktoren von div und fak
expDiff = 0;
while(div % i == 0)
{
expDiff++;
div /= i;
}
for(int j = 3; expDiff != 0 && j <= fac; j++)
{
int temp = j;
while(expDiff != 0 && temp % i == 0)
{
expDiff--;
temp /= i;
}
/* DEESSHALB, wegen so nem verdammten "Fehler" hab ich kein accepted bekommen -.-
* Sowas sieht man doch nicht, war bei mir bloßer Zufall und Stundenlanges rumprobieren...
* ganz ehrlich, nervig
*
* if(expDiff == 0)
* break;
*/
}
if(expDiff > 0)
return false;
}
//wenn alle schleifen durchgelaufen sind, dann muss div entweder 1 oder eine primzahl sein, da sie keine teiler bis sqrt(div) hat
if(div > 1 && div > fac)
return false;
return true;
}
public static void main(String[] args)
{
try{
//Buffered reader ist nochmal um einiges schneller als Scanner!
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(input.readLine());
while(true)
{
int fac = Integer.parseInt(tokenizer.nextToken());
int div = Integer.parseInt(tokenizer.nextToken());
boolean divides = dividesFac(fac, div);
System.out.println(div+(divides?" divides ":" does not divide ")+fac+"!");
tokenizer = new StringTokenizer(input.readLine());
if(!tokenizer.hasMoreTokens())
System.exit(0);
}}catch(Exception e){}
}
}

8.

/**
* Angewandte Mathematik, SS11
* Problem: 10139 Factovisors
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1080
*
* @author Weber Christian
* @author Waldleitner Christoph
* @author Wolff Marco
* @version 1.0, 04/12/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.412
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Factovisors
{

/**
* @param args
*/
public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = "";

while (!s.equals(" "))
{
s = br.readLine();
int faku = 0;
int other = 0;
int otherCopy = 0;

try
{
String[] splitted = s.split(" ");
faku = Integer.parseInt(splitted[0]);
other = Integer.parseInt(splitted[1]);
otherCopy = other;

} catch (Exception e)
{
break;
}

if (faku >= other)
{
System.out.println(other + " divides " + faku + "!");
continue;
}
if (other == 0)
{
System.out.println(other + " does not divide " + faku + "!");
continue;
}
if (other == 1)
{
System.out.println(other + " divides " + faku + "!");
continue;
}
if (faku == 0 || faku == 1)
{
System.out.println(other + " does not divide " + faku + "!");
continue;
}

Map<Integer, Integer> primfaktors = new HashMap<Integer, Integer>();

for(int i=2;i<=3;i++)
{
if(other%i==0)
{
int Anzahl = 1;
other/=i;
while(other%i == 0)
{
Anzahl++;
other/=i;
}
primfaktors.put(i, Anzahl);
}
}

long t = 5;
int diff = 2;
while (t * t <= other)
{
int e = 0;
while (other % t == 0)
{
e++;
other /= t;
}
if (e != 0)
primfaktors.put((int) t, e);
t += diff;
diff = 6 - diff;
}
if(other > 1)
{
primfaktors.put(other,1);
}

boolean ok = false;
for (Map.Entry<Integer, Integer> primeFactor : primfaktors.entrySet())
{
ok = false;
if(primeFactor.getValue() == 1)
{
if(faku<primeFactor.getKey())
{
ok = false;
break;
}
}
int Anzahl2 = 0;
for (long j=primeFactor.getKey();j<=faku;j++)
{
long number = j;
if(number%primeFactor.getKey() == 0)
{
Anzahl2++;
number/=primeFactor.getKey();

while(number%primeFactor.getKey() == 0)
{
Anzahl2++;
number/=primeFactor.getKey();
}

if(Anzahl2 >= primeFactor.getValue())
{
ok = true;
break;
}
}
}

if(Anzahl2 < primeFactor.getValue())
{
ok = false;
break;
}

if (!ok)
{
break;
}
}

if (ok)
{
System.out.println(otherCopy + " divides " + faku + "!");
} else
{
System.out
.println(otherCopy + " does not divide " + faku + "!");
}

}
}
}


/*for (int i = faku; i >= 2; i--)
{
if (i % primeFactor.getKey() == 0)
{
long count = i / primeFactor.getKey();

ok = count >= primeFactor.getValue();
break;
}
}*/

/*
for(int j = primeFactor.getKey(); j<=faku;j+=primeFactor.getKey())
{
counter++;
if(counter >= primeFactor.getValue())
{
ok = true;
break;
}
}
*/

/*
int Anzahl2 = 0;
for (long j=primeFactor.getKey();j<=faku;j++)
{
long number = j;
if(number%primeFactor.getKey() == 0)
{
Anzahl2++;
number/=primeFactor.getKey();

while(number%primeFactor.getKey() == 0)
{
Anzahl2++;
number/=primeFactor.getKey();
}

if(Anzahl2 >= primeFactor.getValue())
{
ok = true;
break;
}
}
}

if(Anzahl2 < primeFactor.getValue())
{
ok = false;
break;
}*/


9.

/**
* Angewandte Mathematik, SS11
* Problem: 10139 - Factovisors
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_pro
blem&problem=1080
*
* @author Brielbeck, Daniel
* @author Weber, Georg
* @version 1.0, 04/10/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime:
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input;
BigDecimal sum;
BigDecimal ver;
BigDecimal teiler;
while ((input = reader.readLine()) != null) {
boolean teilbar = false;
int n = Integer.parseInt(input.split(" ")[0]);
int m = Integer.parseInt(input.split(" ")[1]);
sum = new BigDecimal("1");
ver = new BigDecimal("0");
teiler = new BigDecimal(input.split(" ")[1]);
for (int i = n; i > 1; i--) sum = sum.multiply(new BigDecimal(String.valueOf(i)));
do{
ver.add(teiler);
if(sum==ver){
teilbar=true;
if(sum>ver){
teilbar=false;
break;
}
}
} while(true);
if(teilbar) System.out.println(input.split(" ")[1]+" divides "+ input.split("
")[0]+"!");
else System.out.println(input.split(" ")[1]+" does not divide "+ input.split("
")[0]+"!");
}
}
public static boolean ganzzahlig(BigDecimal y){
return true;
}
}

--------------------------------------------------------------------
1.

/*
* ACM Contest training
* Problem: 10139 - Factovisors
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1080
*
* @author Christoph Goettschkes
* @version 1.0, 10/27/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.020
*/

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

class Main
{

public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

String line = reader.readLine();

while (true) {
StringTokenizer tokenizer = new StringTokenizer(line);
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());

if (test(n, m))
System.out.println(m + " divides " + n + "!");
else
System.out.println(m + " does not divide " + n + "!");

if (!reader.ready())
break;
line = reader.readLine();
}
}

public static boolean test(int n, int m) {
if (m == 0)
return false;

if (m <= n)
return true;

Map<Integer, Integer> facts = primeFactors(m);

for (int key : facts.keySet()) {
if (getPowers(n, key) < facts.get(key))
return false;
}

return true;
}

public static Map<Integer, Integer> primeFactors(int n) {
Map<Integer, Integer> facts = new HashMap<Integer, Integer>();

int e = 0;
while (n % 2 == 0) {
e++;
n /= 2;
}
if (e != 0)
facts.put(2, e);

e = 0;
while (n % 3 == 0) {
e++;
n /= 3;
}
if (e != 0)
facts.put(3, e);

long t = 5;
int diff = 2;
while (t*t <= n) {
e = 0;
while (n % t == 0) {
e++;
n /= t;
}
if (e != 0)
facts.put((int)t, e);
t += diff;
diff = 6 - diff;
}

if (n > 1)
facts.put(n, 1);

return facts;
}

public static int getPowers(int n, int p) {
int result = 0;
for (long power = p; power <= n; power *= p)
result += n/power;

return result;
}

}




2. Martin Lambeck


package acm_10139_factovisors;

import java.util.LinkedList;
import java.util.Scanner;

public class Main
{

public static void main (String[] args)
{
Scanner sc = new Scanner(System.in);
long fak,div;




while (sc.hasNextLong())
{
fak = sc.nextLong();
div = sc.nextLong();


if (divides(fak, div))
{
System.out.println(div + " divides " + fak + "!");


} else
{
System.out.println(div + " does not divide " + fak + "!");
}

}
}

static long primeCount(long prime, long fak)
{
long sum = 0;
long cont = 0;

sum = fak / prime;
cont = sum;

while (cont > 0)
{
cont = cont / prime;
sum += cont;
}

return sum;
}

static LinkedList<long[]> factor(long num)
{
LinkedList<long[]> factors = new LinkedList<long[]>();
long div = 2;
long mod;
long sqrt = (long) Math.sqrt(num);

while ((num > 1) && (div <= sqrt))
{
mod = num % div;

if (mod == 0)
{
num = num / div;
//System.out.println("")
if ((factors.size() > 0) && (factors.getLast()[0] == div))
{
factors.getLast()[1] += 1;

} else
{
factors.add(new long[]{div, 1});
}

} else
{
if (div == 2)
{
div--;
}

div += 2;
}
}

if (num > 1) //prime
{
factors.add(new long[]{num, 1});
}


return factors;
}

// fak teiler
static boolean divides(long fak, long div)
{
LinkedList<long[]> factors;

if (div == 0)
return false;

if ((div <= fak) || (fak == 0 && div == 1))
return true;

factors = factor(div);


for (long[] prime : factors)
{
if (primeCount(prime[0], fak) < prime[1])
return false;
}

return true;
}

}


2.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem 10139 - Factovisors
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1080
* @author Miesel Christoph
* @author Seilbeck Robert
* @author Wolfram Andre
* @version 1.0 25.03.2009
*
* Status : Accepted
* Runtime: 1.890
*/


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

class Main
{
static int divides(int n, int m)
{
// Anfangsbedingungen richtig stellen
if(n == 1) return 1;
if(n == 0) return 0;
if(m == 0) m = 1;

int sqrtn = (int)Math.sqrt(n);

int p = 0;

// Zahl auf Teilbarkeit mit Divisor 2 prüfen und hoch zählen
while(n%2 == 0)
{
n/=2;
p++;
}
// Fakultät auf Teilbarkeit mit Divisor 2 prüfen und runter zäheln
for(int i = 2; p != 0 && i<=m; i+=2)
{
int t = i;
while(p != 0 && t%2 == 0)
{
t /= 2;
p--;
}
}
// ENDE der Division durch 2
if(p!=0) return 0;


for(int i = 3; n!=1 && i<=sqrtn; i+=2)
{
// ist n durch i teilbar?
if(n%i==0)
{
p=0;
// Zahl auf Teilbarkeit mit ungeraden Divisoren prüfen und hoch zählen
while(n%i==0)
{
p++;
n/=i;
}
for(int j = 3; p!=0&&j<=m;j++)
{
int t=j;
while(p!=0 && t%i==0)
{
t/=i;
p--;
}

}
if(p>0) return 0;

}


}
if(n!=1&&m<n) return 0;
return 1;
}

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

while(sc.hasNext())
{
int fakul = sc.nextInt();
int divisor = sc.nextInt();

if(divides(divisor, fakul) == 0)
System.out.println(divisor+" does not divide "+fakul+"!");
else System.out.println(divisor+" divides "+fakul+"!");
}
}
}

3.

/**
* 10139 - Factovisors
*
* Studiengruppe: IFB2C
*
* Robert Reichart
* Elvin Uzeirovic
* Martin Pesl
*
* Run Time Submission Date
* 1.880 2009-04-20 13:36:43
*/

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

class Main{
DataInputStream in;
int prime[], pow[], len;
int valval[][];
int max = (int) Math.pow(1.0 * ((long) Math.pow(2, 31)), 0.5) + 10;

public Main() throws IOException {
in = new DataInputStream(System.in);


primes();
//Werte einlesen
for (;;) {
int n;
int m;
try {
String s = in.readLine();
if (s.equals(""))
break;
String ss[] = s.split(" ");
n = Integer.valueOf(ss[0]);
m = Integer.valueOf(ss[1]);
}
catch(Exception e) {
break;
}

int mm = m;
// leichten Fähle abdecken
if (m == 0) {
System.out.print(mm + " does not divide " + n + "!\n");
continue;
}
if (m == 1) {
System.out.print(mm + " divides " + n + "!\n");
continue;
}
if (n == 0 || n == 1) {
System.out.print(mm + " does not divide " + n + "!\n");
continue;
}
// richtige überprüfung
boolean flag = true;
//Wurzel der zahl nehmen damit weis man die oberer Grenze
int st = (int) Math.pow(m, 0.5);

for (int i = 0; prime[i] <= st; i++) {

int cnt;
//ermitteln wie oft die Primzahl in m reinpast(exponenten ermitteln)
for (cnt = 0; m % prime[i] == 0; cnt++)
m /= prime[i];
// abspeichern in pow
pow[i] = cnt;

if (pow[i] == 0)
continue;
// überprüfen ob der wert primzahl^(cnt-1) >n ist
int req = valval[i][pow[i] - 1];
if (req > n) {
flag = false;
break;
}
if (m == 1)
break;

}
if (flag) {
if (m == 1 || m <= n) {
System.out.print(mm + " divides " + n + "!\n");
continue;
}

}
System.out.print(mm + " does not divide " + n + "!\n");
}
}
//alle Primzahlen ermitteln und ins prime Array schreiben
void primes() {
prime = new int[max];
pow = new int[max];
len = 0;
boolean flag[] = new boolean[max];
Arrays.fill(flag, true);
for (int i = 2; i < max; i++) {
if (!flag[i])
continue;
prime[len++] = i;
for (int j = i; (long) i * j < max; j++)
flag[i * j] = false;

}

fill1();
}
// Jedes vielfache der Primzahl in ein Array rein
void fill1() {
valval = new int[len][];
for (int i = 0; i < len; i++) {
// ermitteln wie oft die Primzahl Maximal reingeht
int now = (int) (Math.log(Math.pow(2, 31) - 1) / Math.log(prime[i]));
//Werte reservieren im Array
valval[i] = new int[now];
int j = 0;
for (int k = prime[i]; j < now; k += prime[i]) {


for (int l = k; l % prime[i] == 0 && j < now; l /= prime[i])
//vielfache von der Primzahl im Array Speichern
valval[i][j++] = k;

}

}

}


public static void main(String args[]) throws IOException {
Main m = new Main();
}
}



4.

/**
* ACM
* UVa Status: accepted
* Run Time: 1.500
* Category: Math
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {


private static boolean divides(int n,int f)
{
if(n == 0)
return false;
if(n == 1)
return true;
if(f == 0) // if n != 1 => n does not divide 1
return false;

if(f > n)
return true;

int p=0;
int sqrt = (int)Math.sqrt(n);

for(int j=2; n > 1 && j <= sqrt; j+= (j==2)? 1 : 2)
if(n%j == 0)
{
while(n%j == 0)
{
n /= j;
p++;
}

for(int i=j, tmp = i; p>0 && i <= f; i+=j, tmp = i)
while(tmp%j == 0 && p>0)
{
tmp /= j;
p--;
}
}

if(p > 0)
return false;

if(n > 1 && n > f)
return false;

return true;

}


public static void main(String...args)
{
int f,n;
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt())
{
f = scanner.nextInt();
n = scanner.nextInt();

if(divides(n,f))
System.out.printf("%d divides %d!\n", n, f);
else
System.out.printf("%d does not divide %d!\n", n, f);
}

}

}


5.

/**
* Angewandte Mathematik SS 09
10139 Factovisors
* UVa Status: Accepted
* Run Time: 0.850
* Programming Language: C
* @author Doina Logofatu logofatu@hm.edu
*/

/*
tests if n divides m!
*/
int divides(int n, int m){

int t, i, j, p=0;
int sqrtn;

if(n==1) return 1;
if(n==0) return 0; /* 0 does not divide anything */


if(0==m) m=1; /* 0! = 1! = 1 */

sqrtn = (int)sqrt(n);

/* for 2 divisor of n we count the number of 2s n = 2*2*..*2*T
2 p times;
then we count how many times comes 2 in m!, too less => p>0
=> n doesnt divide m!
*/
if(n%2==0) while(n%2==0) {p++; n/=2; }
for(i=2; p!=0 &&i<=m; i+=2){
t=i;
while(p!=0 && t%2==0){t/=2; p--;}
}
if(p!=0) return 0;

/* for i prime divisor of n we count the number of is n = i*i*..*i*T
i p times;
then we count how many times comes i in m!, too less => p>0
=> n doesnt divide m!
*/
for(i=3; n!=1 && i<=sqrtn; i+=2){

if(n%i==0){
p=0;
while(n%i==0) {p++; n/=i; }

for(j=3; p!=0 && j<=m; j++){
t=j;
while(p!=0 && t%i==0){t/=i; p--;}
}

if(p!=0) return 0;

}

}

/*
n is prime now, we check m>=n, if not so
then n doesnt divide m!
*/
if(n!=1 && m<n) return 0;
return 1;

}

int main() {

int n, m;

while(scanf("%d%d", &n, &m)==2) {

printf("%d ", m);
divides(m, n)?printf("divides "):printf("does not divide ");
printf("%d!\n", n);

}

return 0;
}