AtCoder CADDi C - Product and GCD Difficulty: 772
This theme, prime factorization + hash
Ruby
When the 972439611840
of input example 4 is factorized into prime factors, it becomes{2 => 6, 3 => 3, 5 => 1, 103 => 4}
.
Divide this into N integers to get the answer. Less than N prime numbers do not contribute to the greatest common divisor.
ruby.rb
require 'prime'
n, p = gets.split.map(&:to_i)
if p == 1
puts 1
elsif n == 1
puts p
else
h = Prime.prime_division(p).to_h
ans = 1
h.each do |k, v|
while v >= n
ans *= k
v -= n
end
end
puts ans
end
prime.rb
require 'prime'
h = Prime.prime_division(p).to_h
prime
library that handles prime numbers, and prime_division
does prime factorization. ~~ It's too cheat. ~~
You can also generate prime numbers with generator.next
, so the prime problem seems to have an advantage in *** Ruby ***.
Pythonpython.py
from collections import defaultdict
from math import sqrt
n, p = map(int, input().split())
h = defaultdict(int)
def factorization(arg):
while arg % 2 == 0:
h[2] += 1
arg /= 2
for i in range(3, int(sqrt(arg)) + 1, 2):
while arg % i == 0:
h[i] += 1
arg /= i
if arg > 1:
h[arg] += 1
if p == 1:
print(1)
elif n == 1:
print(p)
else:
factorization(p)
ans = 1
for k, v in h.items():
while v >= n:
ans *= k
v -= n
print(ans)
def.py
def factorization(arg):
I defined a function for the first time in * Python *, but it seems that an error will occur if I do not define it before using it. Perl
perl.pl
chomp (my ($n, $p) = split / /, <STDIN>);
my %h;
if ($p==1) {
print "1\n";
} elsif ($n==1) {
print "$p\n";
} else {
factorization($p);
my $ans = 1;
for my $k (keys %h) {
my $v = $h{$k};
while ($v >= $n) {
$ans *= $k;
$v -= $n;
}
}
print "$ans\n";
}
sub factorization {
my $arg = shift;
while ($arg % 2 == 0) {
$h{2}++;
$arg /= 2;
}
for my $i (3..sqrt($arg)) {
if ($arg % $i == 0) {
$h{$i}++;
return ($i, factorization($arg / $i));
}
}
$h{$arg}++ if $arg > 1;
}
fac.pl
sub factorization {
my $arg = shift;
while ($arg % 2 == 0) {
$h{2}++;
$arg /= 2;
}
for my $i (3..sqrt($arg)) {
if ($arg % $i == 0) {
$h{$i}++;
return ($i, factorization($arg / $i));
}
}
$h{$arg}++ if $arg > 1;
}
For the prime factorization function, refer to @ sugyan's * How to make a prime factorization one-liner, part 1 *. Java
java.java
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = Long.parseLong(sc.next());
long p = Long.parseLong(sc.next());
sc.close();
if (p == 1) {
System.out.println(1);
} else if (n == 1) {
System.out.println(p);
} else {
HashMap<Long, Long> h = factorization(p);
long ans = 1;
for (long k : h.keySet()) {
long v = h.get(k);
while (v >= n) {
ans *= k;
v -= n;
}
}
System.out.println(ans);
}
}
static HashMap<Long, Long> factorization(long p) {
HashMap<Long, Long> h = new HashMap<>();
while (p % 2 == 0) {
if (h.containsKey(2L)) {
h.put(2L, h.get(2L) + 1);
} else {
h.put(2L, 1L);
}
p /= 2;
}
for (long i = 3; i * i <= p; i += 2) {
while (p % i == 0) {
if (h.containsKey(i)) {
h.put(i, h.get(i) + 1);
} else {
h.put(i, 1L);
}
p /= i;
}
}
if (p > 1)
h.put(p, 1L);
return h;
}
}
For the prime factorization function, refer to * Introduction to Easy Java Programming *.
Ruby | Python | Perl | Java | |
---|---|---|---|---|
Code length | 247 Byte | 567 Byte | 571 Byte | 1419 Byte |
Execution time | 24 ms | 87 ms | 11 ms | 104 ms |
memory | 3964 KB | 3316 KB | 512 KB | 23892 KB |
Referenced site
Recommended Posts