[PYTHON] Ich habe an AtCoder teilgenommen (ABC169 Edition)

Hallo! Dies ist Roadrice Field, ein Meisterschüler der Bioinformatik! Es ist eine Weile her, seit ich das letzte Mal gestorben bin, aber seit ich an ABC169 teilgenommen habe, schreibe bitte den Eintrag auf.

Problem A

Das Multiplizieren von bis zu 3 Ziffern wird von der 3. Klasse der Grundschule gemäß den aktuellen Unterrichtsrichtlinien gelernt.

Meine Antwort

A.py

A,B = map(int, input().split())
print(A*B)

B-Problem

Ich habe es genau so implementiert, wie es einmal geschrieben wurde.

B.py

N = int(input())
A = list(map(int, input().split()))

ans = 1
for i in range(N):
    ans *= A[i]

if ans <= 1e18: print(ans)
else: print(-1)

Das Ergebnis ist "TLE". Die Zahlen sind groß, oder?

Wenn die Eingabe 0 enthält, lautet die Antwort zu diesem Zeitpunkt 0. Wenn also zuerst beurteilt wird, ob die Eingabe 0 enthält, wird "0" ohne Multiplikation ausgegeben und der Prozess endet, 10 18 während der Berechnung. Ich dachte, dass es schneller sein würde, wenn ich es kaputt mache und "-1" ausgeben würde, wenn es </ sup> überschreitet, also schrieb ich wie folgt.

B.py

N = int(input())
A = list(map(int, input().split()))

ans = 1
flg = True

if 0 in A: print(0)
else:
    for i in range(N):
        ans *= A[i]
        if ans > 1e18:
            flg = False
            break

    if flg: print(ans)
    else: print(-1)

Dies hat übrigens die Berechnungszeit von maximal "2206 ms" auf "56 ms" reduziert. Mit ein wenig Einfallsreichtum wird sie erheblich schneller sein.

C-Problem

Ich wusste, dass es eine Gleitkomma-Geschichte war, aber es hat nicht geklappt ... Ich habe nicht genug Informationstechnologie studiert ...

D Problem

Ich habe C ++ für dieses Problem verwendet. Sie können die Anzahl der Operationen maximieren, indem Sie die folgenden Schritte ausführen.

Zuerst faktorisieren wir das gegebene * N *.

N = a^{6} \times b^{4} \times c^{3}  

Sei z = a ^{1 </ sup>. Ersetze N durch N / z. Da das gleiche z nicht ausgewählt werden kann, ist das nächst kleinere a 2 < Wählen Sie / sup> für z. Ersetzen Sie N durch N / z.}

N = a^{3} \times b^{4} \times c^{3}  

Es teilt sich immer noch bei z = a ^{3 </ sup>. Ersetzen Sie N durch N / z.}

N = b^{4} \times c^{3}  

Als nächstes dividieren Sie durch z = b ^{1 </ sup> ...}

Teilen Sie wiederholt durch die 1., 2. und 3. Potenz der Primfaktoren, und wenn die Primfaktoren in * N * erschöpft sind, dividieren Sie durch die 1., 2. und 3. Potenz der nächsten Primfaktoren. Sie müssen den Vorgang nur wiederholen.

Meine Antwort

D.cpp

#include<bits/stdc++.h>
using namespace std;

vector<long long> pri_fac(long long N){
    vector<long long> yakusu;
    long long now = 0; 
    long long a = 2;
        while(N >= a*a){
            if(N%a == 0){
                yakusu.push_back(a);
                 N /= a;
            }else{
                a++;
            }
        } 
    if(N != 1) yakusu.push_back(N);
    return yakusu;
}

int main(){
    long long N;
    cin >> N;

    vector<long long> vec_all;
    vec_all = pri_fac(N);

    if(N == 1) cout << 0 << endl;
    else if(vec_all.size() == 1) cout << 1 << endl;
    else{
        long long now;
        now = vec_all[0];
        vector<long long> unique_count;
        unique_count.push_back(1);
        for(long long i=1;i<vec_all.size();i++){
            if(vec_all[i] != now) unique_count.push_back(1);
            else unique_count[unique_count.size()-1]++;
            now = vec_all[i];
        }

        long long ans = 0;

        for(long long i=0;i<unique_count.size();i++){
            long long j = 1;
            while(j <= unique_count[i]){
                ans++;
                unique_count[i] -= j;
                j++;
            } 
        }

        cout << ans << endl;
    }
    return 0;
}

Wenn * N * 1 oder eine Primzahl ist, wollte ich keinen Fehler, daher behandle ich zuerst Ausnahmen. Pri_fac ist eine Funktion, die eine Primfaktorzerlegung durchführt und Primfaktoren zum Vektor zurückschiebt.