Einführung

Ich hatte die Gelegenheit, eine ausführliche Erklärung zu E-Problem von AtCoder Beginner Contest 177 zu schreiben. Es war besser als ich erwartet hatte, also werde ich es als Artikel zusammenfassen.

Erwägung

Unter Problem kann der Fokus in der folgenden Reihenfolge in drei Bereiche unterteilt werden.

"GCD (A_i, A_j) = 1 für alle 1 ≤ i <j ≤ N" gilt.
"GCD (A_1 ... A_N) = 1" gilt
Weder gilt

Von nun an werden wir uns diese drei genauer ansehen.

1. "GCD (A_i, A_j) = 1 für alle 1 ≤ i <j ≤ N" gilt.

Fragen Sie in jedem Fall ehrlich.

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

Aufgrund der Einschränkung ist $ 2 ≤ N ≤ 10 ^ 6 $, sodass das Maximum $ O (10 ^ {12}) $ ist und das Ausführungszeitlimit von 2 Sekunden nicht eingehalten werden kann.

Achten Sie hier darauf, dass die maximale Verpflichtungszahl einer Kombination 1 beträgt. Dies bedeutet, dass jede Kombination von ganzen Zahlen $ (A_i, A_j) $ Primzahlen zueinander sind.

Daher werden alle N ganzen Zahlen in Primfaktoren zerlegt, und wenn dieselben Primfaktoren nicht auftreten, gilt dies, und es wird "paarweises Koprime" ausgegeben.

2. "GCD (A_1 ... A_N) = 1" gilt

Dies ist O (N), auch wenn es ehrlich gedreht wird, sodass kein Raum für Überlegungen besteht.

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

Wenn 1 nicht hält und "res == 1", sollte "setwise coprime" ausgegeben werden. Und wenn keiner von 3. wahr ist, wird "nicht Coprime" ausgegeben.

Daraus ergibt sich 1 als Hauptüberlegung.

Primfaktorisierung

Ruby hat ein Prime-Modul, das aus Prime.prime_division berücksichtigt werden kann. Referenz: Spielen mit Primzahlen in Ruby (Primmodul)

Dies scheint leicht zu lösen zu sein. Einreichen!

Nicht in der Zeit. Was sollen wir dann tun?

osa_k Methode

Es ist am schnellsten, einen Blick auf [Eratostenes 'Sieb und schnelle Primfaktorisierung] zu werfen (https://blog.manuel1024.com/archives/79), aber ich werde es auch hier auf meine eigene Weise erklären.

Dies ist ein Algorithmus, der positive ganze Zahlen kleiner oder gleich N (in diesem Fall $ A_ {max} $) in Primfaktoren zerlegt. Mach O (log M) $). Der Berechnungsbetrag beträgt $ O (log M) $ von $ O (log log N + log M) $. Ab diesem Maximalwert $ A_ {max} = 10 ^ 6 $ ist es ungefähr $ O (log 10 ^ 6) = O (10) $. Daher beträgt der Berechnungsaufwand zum Ermitteln der Primfaktoren aller N ganzen Zahlen ungefähr $ O (N log A_ {max}) = O (10 ^ 7) $, was ausreichend ist.

Zusammenfassend,

Zerlegen Sie eine positive ganze Zahl in Primfaktoren
Führen Sie eine Vorverarbeitung durch, um den minimalen Primfaktor zu ermitteln
Hochgeschwindigkeits-Primfaktorisierung unter Verwendung vorverarbeiteter Ergebnisse

Ist ein Algorithmus

Vorverarbeitung

Finden Sie den minimalen Primfaktor min_factor für ganze Zahlen (1 ~ N) kleiner oder gleich $ N = A_ {max} $. Betrachten Sie bei der Anwendung des Erratostinesiebs mehrere k von i (= 2 ~ $ \ sqrt {N} $) in der angegebenen Reihenfolge. Wenn i kleiner als der in k enthaltene Wert ist, geben Sie i ein.

Beispiel: Nehmen wir zum Beispiel den Maximalwert N = 16 des Wertes, der in Primfaktoren berücksichtigt werden soll. Da $ \ sqrt {16} = 4 $ ist, beträgt der Bereich von i 2 ~ 4.

Schauen Sie sich i der Reihe nach an und erstellen Sie ein Array min_factor, in dem die kleinsten Primfaktoren gespeichert sind.

Der letzte Teil ist die Sequenz min_factor.

Dieser Prozess

Bitte beachten Sie das folgende Flussdiagramm.

Das Ergebnis der Primfaktorisierung wird im Ergebnis gespeichert. Da dieselbe Primzahl mehrmals gespeichert wird, verwenden Sie "uniq" oder "set", wenn Sie nur Primfaktoren möchten.

Wenn das obige Beispiel auf den obigen Fluss angewendet wird, wird es wie in der folgenden Abbildung gezeigt.

Es sieht so aus, als könnten Sie damit Code in AC schreiben.

Implementierung

class Osa_k
    # @parm {number} n -Maximaler Wert unter den Werten, die Sie berücksichtigen möchten
    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 -Wert, den Sie berücksichtigen möchten
    # @return {array} res -Primfaktorgruppe von 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 #Maximalwert ist 10^Weil es 6 ist
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) #Verwalten Sie mithilfe assoziativer Sequenzen, ob Primfaktoren bereits aufgetreten sind
is_pairwise_coprime = true #Ob die erste Bedingung erfüllt ist
n.times do |i|
    #Sie müssen es nicht tun, wenn Sie feststellen, dass die erste Bedingung nicht erfüllt ist
    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]) #Überprüfen Sie die zweite Bedingung
end
 
if is_pairwise_coprime then
    puts "pairwise coprime"
elsif res == 1 then
    puts "setwise coprime"
else
    puts "not coprime"
end

Übermittlungsergebnis: https://atcoder.jp/contests/abc177/submissions/16583524

abschließend

AC war dank Eratostenes-Sieb und schnelle Primfaktorisierung möglich. Ich möchte mich hier bei Ihnen bedanken.

ABC177 - E in Ruby lösen