// Online Judge UVa 10139 Factovisors: Accepted
// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1080
import java.io.FileInputStream;
import java.io.IOException;
import java.math.*;
import java.util.*;
import java.util.Map.Entry;
class Main {
private static Scanner in;
public static void main(String[] args) throws IOException {
// helpers for input/output
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;
in = new Scanner(System.in);
if (LOCAL_TEST) {
in = new Scanner(new FileInputStream("E:\\zin.txt"));
}
while (in.hasNextLong()) {
long N = in.nextLong();
long M = in.nextLong();
boolean divides = true;
if (M > N) {
Map<Long, Long> mfactors = GetPrimeFactorsAsMap(M);
Set<Entry<Long, Long>> mf = mfactors.entrySet();
Map<Long, Long> nfactors = GetPrimeFactorsOfFact(N, mfactors);
// Set<Long> sss = nfactors.keySet();
// for (Long k : sss) {
// System.out.print(k + "^" + nfactors.get(k) + " ");
// }
// System.out.println();
for (Entry<Long, Long> e : mf) {
Long prime = e.getKey();
Long exp = e.getValue();
if (!nfactors.containsKey(prime)) {
divides = false;
break;
} else if (nfactors.get(prime) < exp) {
divides = false;
break;
}
}
}
if (divides)
System.out.println(M + " divides " + N + "!");
else
System.out.println(M + " does not divide " + N + "!");
}
}
public static List<Long> GetPrimeFactors(long num) {
List<Long> factors = new ArrayList<Long>();
long n = num;
while (n % 2 == 0) {
factors.add(2L);
n = n / 2;
}
long sqrtn = (long) Math.sqrt(n) + 1;
long i = 3;
while (i < sqrtn) {
if (n % i == 0) {
factors.add(i);
n = n / i;
} else {
i = i + 2;
}
}
if (n > 1)
factors.add(n);
return factors;
}
public static Map<Long, Long> GetPrimeFactorsAsMap(long x) {
Map<Long, Long> dict = new LinkedHashMap<Long, Long>();
List<Long> f = GetPrimeFactors(x);
for (Long n : f) {
if (!dict.containsKey(n))
dict.put(n, 1L);
else
dict.put(n, dict.get(n) + 1);
}
return dict;
}
public static Map<Long, Long> GetPrimeFactorsOfFact(long x,
Map<Long, Long> mfactors) {
Map<Long, Long> dict = new LinkedHashMap<Long, Long>();
// List<Long> primes = GetPrimeNumsLessThanOrEqual2(sx);
List<Long> primes = new ArrayList<Long>();
primes.addAll(mfactors.keySet());
for (Long p : primes) {
long pk = p;
long nfactors = 0;
while (true) {
if (x / pk > 0) {
nfactors += (x / pk);
pk = pk * p;
} else
break;
}
if (nfactors > 0)
dict.put(p, nfactors);
}
return dict;
}
public static List<Long> GetPrimeNumsLessThanOrEqual2(long maxNum) {
List<Long> p = new ArrayList<Long>();
if (maxNum < 2)
return p;
p.add(2L);
for (long j = 3; j <= maxNum; j += 2) {
boolean isPrime = true;
int N = p.size();
for (int i = 0; i < N; i++) {
long pp = p.get(i);
if (pp * pp > j)
break;
if (j % pp == 0) {
isPrime = false;
break;
}
}
if (isPrime)
p.add(j);
}
return p;
}
}
No comments:
Post a Comment