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