Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search

Introduction

~~ In addition, the language has been updated in the past questions since yesterday. ~~ ** Addition ** It seems that it was once returned to the old environment.

ruby
"2.7.1"

python
Python: 3.8.2
NumPy:  1.18.2
SciPy:  1.4.1

pypy3
Python: 3.6.9

cython
Python: 3.8.2

I didn't know how to check the version of Numo :: NArray.

This theme

AtCoder Beginner Contest C - Digits in Multiplication Difficulty: 834

This theme, prime factorization + bit full search Ruby I solved it before, * AtCoder CADDi 2018 C prime factorization to solve with Ruby, Perl, Java and Python * It seems to be a similar problem, so copy it immediately ~~ ~~ Let's solve it.

ruby.rb


require 'prime'

n = gets.to_i
if n == 1
  puts 1
else
  h = Prime.prime_division(n).to_h
  p = []
  h.each do |k, v|
    while v > 0
      p << k
      v -= 1
    end
  end
  min = Float::INFINITY
  0.upto(2 ** p.size - 1) do |bit|
    a = 1
    b = 1
    p.size.times do |i|
      if bit[i] == 0
        a *= p[i]
      else
        b *= p[i]
      end
    end
    if a >= b
      min = a if min > a
    else
      min = b if min > b
    end
  end
  puts min.to_s.size
end

If you use the method of allocating prime numbers in descending order, you will get WA, so we are using bit full search.

bit.rb


  0.upto(2 ** p.size - 1) do |bit|

  [0, 1].repeated_permutation.each do |bit|

The bit full search also uses repeated_permutation, but here it seems to be TLE. Python

pypy.py


from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > a and a >= b:
            min = a
        elif min > b and b > a:
            min = b
    print(len(str(min)))

int.py


            arg //= i

If it is / =, it seems to be WA.

Ruby(2.3.3) Ruby(2.7.1) Python PyPy3(2.4.0) PyPy3(7.3.0)
Code length(Byte) 506 506 763 763 763
Execution time(ms) TLE 1355 TLE 643 352
memory(KB) 2300 9284 3064 52736 30112

Summary

Recommended Posts

Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby AtCoder ABC110 C String Manipulation
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Benchmark for C, Java and Python with prime factorization
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
Solved AtCoder ABC 114 C-755 with Python3
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
Solve AtCoder ABC166 with python
ABC163 C problem with python3
Full bit search with Python
ABC188 C problem with python3
Solve AtCoder ABC 186 with Python
ABC187 C problem with python
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
AtCoder ABC168 A case expression solved in Ruby and Python
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
Solve ABC163 A ~ C with Python
Scraping with Node, Ruby and Python
Learn search with Python # 2bit search, permutation search
Solve ABC168 A ~ C with Python
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Algorithm in Python (ABC 146 C Binary Search
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
RaspberryPi L Chika with Python and C #
[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!