Ruby と Perl と Java と Python で解く AtCoder CADDi 2018 C 素因数分解

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder CADDi C - Product and GCD
Difficulty: 772

今回のテーマ、素因数分解 ＋ ハッシュ

Ruby

入力例 4 の972439611840を素因数分解しますと、{2=>6, 3=>3, 5=>1, 103=>4}となります。
これを N 個の整数に分配すれば解答が求まります。N 個未満の素数は、最大公約数に寄与しないわけです。

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

Ruby には素数を扱うprimeライブラリが標準であり、prime_divisionで素因数分解をやってくれます。チート過ぎです。
他にもgenerator.nextで素数を生成できますので、素数問題は Ruby にアドバンテージがあると思われます。

Python

python.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):

Python で初めて関数を定義しましたが、使用する前に定義しないとエラーになる様です。

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

素因数分解の関数は、@sugyan さんの*素因数分解ワンライナーの作り方 その１* を参照させていただきました。

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

素因数分解の関数は、お気楽 Java プログラミング入門 を参照させていただきました。

	Ruby	Python	Perl	Java
コード長	247 Byte	567 Byte	571 Byte	1419 Byte
実行時間	24 ms	87 ms	11 ms	104 ms
メモリ	3964 KB	3316 KB	512 KB	23892 KB

まとめ

• CADDi 2018 C を解いた
• Ruby に詳しくなった
• Python に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった

参照したサイト
primeライブラリ
素因数分解ワンライナーの作り方 その１
お気楽 Java プログラミング入門