Résolution avec Ruby, Perl, Java et Python AtCoder CADDi 2018 C factorisation premier

introduction

• Utilisez les recommandations dans AtCoder Problems * pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder CADDi C - Product and GCD Difficulty: 772

Ce thème, décomposition des facteurs premiers + hachage Ruby Lorsque le 972439611840 dans l'exemple d'entrée 4 est factorisé en {2 => 6, 3 => 3, 5 => 1, 103 => 4}. Divisez ceci en N entiers pour obtenir la réponse. Moins de N nombres premiers ne contribuent pas à l'engagement maximum.

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 * a une bibliothèque standard prime qui gère les nombres premiers, et prime_division effectue la factorisation premier. ~~ C'est trop tricher. ~~ Vous pouvez également générer des nombres premiers avec generator.next, donc le problème des nombres premiers semble avoir un avantage sur *** 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):

J'ai défini une fonction pour la première fois en * Python *, mais il semble qu'une erreur se produira si je ne la définit pas avant de l'utiliser. 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;
}

Pour la fonction de factorisation première, référez-vous à @ sugyan's * Comment faire un one-liner de factorisation premier, partie 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;
    }
}

Pour la fonction de factorisation principale, reportez-vous à * Introduction à la programmation Java facile *.

Résumé

• Résolu CADDi 2018 C
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java

Site référencé

• bibliothèque principale *
• Comment faire une première ligne de décomposition des facteurs premiers, partie 1 *
• Introduction à la programmation Java facile *