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