ABC177-Résoudre E avec Ruby

introduction

J'ai eu l'occasion d'écrire une explication détaillée sur E problem du AtCoder Beginner Contest 177. C'était mieux que ce à quoi je m'attendais, je vais donc le résumer sous forme d'article.

Considération

Depuis Problème, le focus peut être divisé en trois dans l'ordre suivant.

1. "GCD (A_i, A_j) = 1 pour tout 1 ≤ i <j ≤ N" est valable.
2. "GCD (A_1 …… A_N) = 1" tient
3. Aucun des deux

À partir de maintenant, nous examinerons ces trois plus en détail.

1. "GCD (A_i, A_j) = 1 pour tout 1 ≤ i <j ≤ N" est valable.

Demandez honnêtement dans tous les cas.

N.times do |i|
  N.times do |j|
    if A[i].gcd(A[j]) != 1 then
      is_pairwise_coprime = false
    end
  end
end

En raison de la contrainte, $ 2 ≤ N ≤ 10 ^ 6 $, donc le maximum est $ O (10 ^ {12}) $ et le délai d'exécution de 2 secondes ne peut pas être respecté.

Notez le fait que «l'engagement maximum de toute combinaison est de 1». Cela se traduit par une combinaison d'entiers $ (A_i, A_j) $ premiers les uns par rapport aux autres.

Par conséquent, tous les N entiers sont décomposés en facteurs premiers, et si les mêmes facteurs premiers n'apparaissent pas, cela est vrai, et «coprime par paires» est affiché.

2. "GCD (A_1 …… A_N) = 1" tient

C'est O (N) même s'il est tourné honnêtement, donc il n'y a pas de place pour la considération.

res = a[0]
a.each do |elm|
  res = res.gcd(elm)
end

Quand 1 ne tient pas et res == 1, setwise coprime doit être affiché. Et, quand aucun des 3. n'est satisfait, "pas coprime" est affiché.

À partir de là, 1 est la principale considération.

Factorisation prime

Ruby a un module principal, qui peut être factorisé à partir de Prime.prime_division. Référence: Jouer avec les nombres premiers en Ruby (module premier)

Cela semble facile à résoudre. Soumettre!

Pas à temps. Alors que devons-nous faire.

Méthode osa_k

C'est le plus rapide pour jeter un coup d'œil sur le tamis d'Eratostène et la factorisation rapide des nombres premiers, mais je vais également l'expliquer à ma manière ici.

Il s'agit d'un algorithme qui décompose les entiers positifs inférieurs ou égaux à N ($ A_ {max} $ dans ce cas) en facteurs premiers. Faites O (log M) $). Le montant du calcul est $ O (log M) $ à partir de $ O (log log N + log M) $. A partir de cette valeur maximum $ A_ {max} = 10 ^ 6 $, ce sera environ $ O (log 10 ^ 6) = O (10) $. Par conséquent, la quantité de calcul pour trouver les facteurs premiers de tous les N entiers est d'environ $ O (N log A_ {max}) = O (10 ^ 7) $, ce qui est suffisant.

En résumé,

• Décomposer un entier positif en facteurs premiers --Effectuer un prétraitement pour trouver le facteur premier minimum --Factorisation des nombres premiers à haute vitesse à l'aide de résultats prétraités

Est un algorithme

Prétraitement

Trouvez le facteur premier minimum min_factor pour les entiers (1 ~ N) inférieurs ou égaux à $ N = A_ {max} $. Dans l'application du tamis d'ératostines, regardez plusieurs k de i (= 2 ~ $ \ sqrt {N} $) dans l'ordre, et si i est plus petit que la valeur contenue dans k, entrez i.

Exemple: Prenons, par exemple, la valeur maximale N = 16 de la valeur à prendre en compte en facteurs premiers. Puisque $ \ sqrt {16} = 4 $, la plage de i est comprise entre 2 et 4.

Regardez i dans l'ordre et créez un tableau min_factor qui stocke les plus petits facteurs premiers.

La dernière partie est la séquence min_factor.

Ce processus

Veuillez vous référer à l'organigramme suivant.

Le résultat de la factorisation prime est stocké dans result. Puisque le même nombre premier est stocké plusieurs fois, utilisez ʻuniq ou set` si vous ne voulez que des facteurs premiers.

Lorsque l'exemple ci-dessus est appliqué au flux ci-dessus, il devient comme indiqué dans la figure ci-dessous.

Il semble que vous pouvez écrire du code dans AC avec cela.

la mise en oeuvre

class Osa_k
    # @parm {number} n -Valeur maximale parmi les valeurs que vous souhaitez factoriser
    def initialize(n)
        @min_factor = [*0..n]
        i = 2
        while i * i <= n do
            if @min_factor[i] == i then
                j = 2
                while i * j <= n do
                    @min_factor[i*j] = i if @min_factor[i*j] > i
                    j += 1
                end
            end
            i += 1
        end
    end
 
    # @parm {number} m -Valeur à prendre en compte
    # @return {array} res -Groupe de facteurs premiers de m
    def factor(m)
        res = []
        tmp = m
        while tmp > 1 do
            res << @min_factor[tmp]
            tmp /= @min_factor[tmp]
        end
        return res.uniq
    end
end
 
MAX = 10 ** 6 + 10 #La valeur maximale est de 10^Parce que c'est 6
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)
osa_k = Osa_k.new(MAX)
res = a[0]
h = Hash.new(0) #Gérer si les facteurs premiers sont déjà apparus à l'aide de séquences associatives
is_pairwise_coprime = true #Si la première condition est remplie
n.times do |i|
    #Vous n'êtes pas obligé de le faire lorsque vous constatez que la première condition n'est pas remplie
    if is_pairwise_coprime then
        osa_k.factor(a[i]).each do |num, cnt|
            if h.has_key?(num) then
                is_pairwise_coprime = false
                break
            end
            h[num] += 1
        end
    end
    res = res.gcd(a[i]) #Vérifiez la deuxième condition
end
 
if is_pairwise_coprime then
    puts "pairwise coprime"
elsif res == 1 then
    puts "setwise coprime"
else
    puts "not coprime"
end

Résultat de la soumission: https://atcoder.jp/contests/abc177/submissions/16583524

en conclusion

Grâce au tamis d'Eratostène et à la factorisation rapide des nombres premiers, j'ai pu AC. Je voudrais vous remercier ici.