Résolution avec Ruby et Python AtCoder ARC067 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 Regular Contest C - Factors of Factorial Difficulty: 925

Ce thème, décomposition des facteurs premiers

Des problèmes tels qu'une version simplifiée de l'exploration de bits de factorisation principale d'AtCoder ABC057 C précédemment résolue en Ruby et Python](https://qiita.com/superrino130/items/10213645bb4ff63a6ac7) *.

Bien que cela soit appelé revêtement de sol, lorsque vous faites réellement un revêtement de sol, le débordement d'entier est visible dans le système de langage C, de sorte que ce point peut être ** Difficulté ** supérieur. Ruby

ruby.rb

require 'prime'

n = gets.to_i
if n == 1
  puts '1'
  exit
end
M = 10 ** 9 + 7
h = Hash.new(0)
1.upto(n) do |i|
  i.prime_division.each do |k, v|
    h[k] += v
  end
end
puts h.values.map{|i| (i + 1)}.inject{|u, v| u * v % M}

prime.rb

1.upto(n) do |i|
  i.prime_division.each do |k, v|
    h[k] += v
  end
end

Aucun calcul de mise à l'échelle n'est requis et les nombres de la séquence de nombres à mettre à l'échelle sont factorisés et insérés dans le hachage. ** Addenda ** J'ai reçu un commentaire, alors je l'ai corrigé.

perm.rb

puts h.values.map{|i| (i + 1)}.inject{|u, v| u * v % M}

Puisqu'il y a des cas où un certain nombre premier n'est pas sélectionné (zéro est sélectionné), (i + 1) est utilisé pour obtenir le nombre de combinaisons.

Rubis de côté

À propos, la puissance de la valeur maximale «1000» de «1 ≤ N ≤ 1000» est une valeur numérique de «2568 chiffres».

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Même si ce nombre est directement Prime.prime_division (1000!), Il sera factorisé normalement, résultant en ʻAC. Juste un peu ! «Je l'ai fait. Python

python.py

from math import sqrt
from collections import defaultdict

n = int(input())
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 n == 1:
    print(1)
else:
    m = 10 ** 9 + 7
    for i in range(1, n + 1):
        factorization(i)
    cnt = 1
    for key, v in h.items():
        cnt *= (v + 1)
        cnt %= m
    print(cnt)

J'ajoute un nombre premier à «defaultdict» avec ma propre «fonction de factorisation».

Résumé

• ARC 067 C résolu
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python