Lösen mit Ruby, Perl, Java und Python AtCoder CADDi 2018 C Primfaktorisierung

Einführung

• AtCoder-Probleme * Verwendet Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder CADDi C - Product and GCD Difficulty: 772

Dieses Thema, Primfaktor Zerlegung + Hash Ruby Wenn der "972439611840" in Eingabebeispiel 4 in "{2 => 6, 3 => 3, 5 => 1, 103 => 4}" faktorisiert wird. Teilen Sie dies in N ganze Zahlen, um die Antwort zu erhalten. Weniger als N Primzahlen tragen nicht zum maximalen Engagement bei.

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 * hat eine Standard-Prime-Bibliothek, die Primzahlen verarbeitet, und Prime_Division übernimmt die Primfaktorisierung. ~~ Es ist zu betrügen. ~~ Sie können auch Primzahlen mit generator.next generieren, sodass das Primzahlenproblem einen Vorteil gegenüber *** Ruby *** zu haben scheint. 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):

Ich habe eine Funktion zum ersten Mal in * Python * definiert, aber es scheint, dass ein Fehler auftritt, wenn ich sie vor der Verwendung nicht definiere. 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;
}

Informationen zur Funktion der Primfaktorisierung finden Sie in @ sugyans * So erstellen Sie eine Primfaktorisierung einzeilig, Teil 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;
    }
}

Informationen zur Primfaktorisierungsfunktion finden Sie unter * Einführung in die einfache Java-Programmierung *.

Zusammenfassung

• Gelöstes CADDi 2018 C.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut
• Machen Sie sich mit Perl vertraut
• Machen Sie sich mit Java vertraut

Referenzierte Site

• Hauptbibliothek *
• Wie man eine Primfaktor-Zerlegung einzeilig macht Teil 1 *
• Einführung in die einfache Java-Programmierung *