Problem ze zrozumieniem i implementacja odpowiedzi do zadania

0

Mam takie zadanie
Przypomnijmy, że liczba doskonała to liczba naturalna większa od 1, która, jest sumą wszystkich swoich dzielników właściwych. Liczbą doskonałą drugiego rodzaju nazywamy liczbę naturalną większą od 1, która jest iloczynem wszystkich swoich dzielników właściwych. Przykładowo dzielnikami właściwymi liczby 27 są 1, 3 i 9, a więc 27 jest liczbą doskonałą drugiego rodzaju: 1 · 3 · 9 = 27. Dzielnik właściwy to dzielnik naturalny liczby, różny od niej samej. Chcielibyśmy się dowiedzieć, ile jest liczb doskonałych drugiego rodzaju zawartych w pewnych przedziałach.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita d (1<= d <= 30)
oznaczająca liczbę przypadków testowych. Kolejnych d wierszy zawiera po
dwie liczby całkowite a i b (2 <= a < b ¬<=1 000 000).
Wyjście
Dla każdego przypadku testowego należy wypisać jedną liczbę całkowitą
równą liczbie liczb doskonałych drugiego rodzaju zawartych w przedziale
[a..b].

I taka odpowiedź

Zadanie można rozwiązać w czasie O(d + k log log k), gdzie k to największa
wartość ze wszystkich końców przedziałów.
• Wiele liczb półpierwszych jest również liczbami doskonałymi drugiego
rodzaju. Liczby doskonałe drugiego rodzaju nie zawsze są liczbami półpierwszymi. Przykładowo, liczba 27 = 3 · 3 · 3 nie jest półpierwsza.
• Jedynymi liczbami półpierwszymi, które nie są doskonałe, są liczby postaci p^2, gdzie p jest liczbą pierwszą.
• Jedynymi liczbami doskonałymi drugiego rodzaju, które nie są półpierwsze,są liczby postaci p^3, gdzie p jest liczbą pierwszą. Dzielnikami właściwymi
takiej liczby są p i p^2
• Dla każdej liczby zapisujemy, czy jest liczbą doskonałą drugiego rodzaju, po czym tworzymy sumy prefiksowe — liczbę liczb doskonałych w każdym
prefiksie.

for (int i = 2; i * i * i <= k; i++)
    if (F[i] == 0)
        pref[i * i * i] = 1;
for (int i = 2; i <= k; i++) {
    if (F[i] != 0 && F[i / F[i]] == 0 && F[i]*F[i] != i)
        pref[i] = 1;
    pref[i] += pref[i - 1];
}

Mój algorytm

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

int main()
{
    ios_base::sync_with_stdio(0);
    int d, k;
    cin >> d;
    int * przedzialy = new int[d*2];
    for (int i = 0; i < d * 2; i += 2){
        cin >> przedzialy[i] >> przedzialy[i+1];
        k = max(k, przedzialy[i+1]);
    }
    vector <int> F(k+1, 0);
    for (int i = 2; i * i <= k; i++){
        if (F[i] == 0){
            for (int j = i*i; j <= k; j += i)
                if (F[j] == 0)
                    F[j] = i;
        }
    }
    vector <int> pref(k+1, 0);
    for (int i = 2; i * i * i < k; i++){
        if (F[i] == 0)
            pref[i * i * i] = 1;
    }
    for (int i = 2; i <= k; i++) {
        if (F[i] != 0 && F[i / F[i]] == 0 && F[i]*F[i] != i)
            pref[i] = 1;
        pref[i] += pref[i - 1];
    }
    //tablica pref jest dziwna bo dopiero komorka 6 zamiast 5 reprezentuje liczbe 4
    //gdzie popelniam blad?
    for (int i = 0; i < d * 2; i += 2){
        cout << pref[przedzialy[i+1]+1] - pref[przedzialy[i]] << endl;
    }
return 0;
}

Tablica pref w zły sposób reprezentuje liczby, pomoże mi ktoś zrozumieć gdzie robię błąd?

1

Zamotałeś, więc jeśli dobrze zrozumiałem to upraszczając:

Cel: określić sumę liczb doskonałych drugiego rodzaju w danym przedziale.
Liczba doskonała drugiego rodzaju to liczba >1 i zarazem iloczyn swoich dzielników.

Rozwiązanie:

Utwórz zmienne int suma, poczatekPrzedzialu, koniecPrzedzialu;
Utwórz funkcję zwracającą iloczyn dzielników danej liczby;
Bierzemy pierwszą liczbe z przedziału, sprawdzamy czy jest większa niż 1 i czy iloczyn jej dzielników jest jej równy;
Jeśli tak, to : suma +=1; Robimy to w pętli po całym przedziale i wyświetlamy sumę na końcu.

1

Zrób najpierw zadanie w ten sposób, że posiadaj tablicę bool T[] (bądź też wektor, cokolwiek), która odpowiada w komórce k na to czy k jest liczbą doskonałą drugiego rodzaju, i dla każdego zapytania zliczaj jedynki w tej tablicy. Górny limit wyznacz sobie jako największy z końców przedziałów (albo na sztywno, 1000000). Jak to zrobisz poprawnie, to pomogę ze zrobieniem tablicy prefiksowej

1

Jeśli przeanalizujesz dokładnie właściwości liczby doskonałej drugiego rodzaju, to okaże się, że jest to liczba złożona faktorująca się do:

dwóch różnych czynników pierwszych
trzech takich samych czynników pierwszych

Próba znalezienia innej kombinacji, zawsze prowadzi do liczby, której iloczyn wszystkich dzielników dają znacznie większą liczbę.

Górny limit masz 1000000.
Liczb pierszych w tym zakresie nie ma dużo. Sporo można wygenerować nawet za pomocą constexpr (jak to pisałem, to kompilator podał się przy ~3000 a jak teraz próbbowałem to limit był 250000 dla clang i 500000 dla gcc przy domyślnych ustawieniach).
Ja bym się zastanawiam, czy nie da się wygenerować wszystkich tych liczb w rozsądnym czasie. Liczb pierwszych mniejszych niż 1000000 jest ~78500.
Ergo policznie par dających iloczn w zadanym zakresie nie powinno być skomplikowane, a policzanie liczby 3 potęg to jest już trywialne.

0

enedil napisał(a):

Zrób najpierw zadanie w ten sposób, że posiadaj tablicę bool T[] (bądź też wektor, cokolwiek), która odpowiada w komórce k na to czy k jest liczbą doskonałą drugiego rodzaju, i dla każdego zapytania zliczaj jedynki w tej tablicy. Górny limit wyznacz sobie jako największy z końców przedziałów (albo na sztywno, 1000000). Jak to zrobisz poprawnie, to pomogę ze zrobieniem tablicy prefiksowej

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

int main()
{
    ios_base::sync_with_stdio(0);
    const int M = 1000000;
    vector <int> F(M+1, 0);
    vector <int> T(M+1, 0);
    for (int i = 2; i * i <= M; i++){
        if (F[i] == 0)
            for (int k = i*i; k <= M; k += i)
                if (F[k] == 0)
                    F[k] = i;
    }
    for (int i = 2; i * i * i <= M; i++){
        if (F[i] == 0)
            T[i * i * i] = 1;
    }
    for (int i = 2; i <= M; i++){
        if (F[i] != 0 && F[i / F[i]] == 0 && F[i] * F[i] != i)
            T[i] = 1;
    }
    int d, a, b, ile;
    cin >> d;
    for(int i = 0; i < d; i++){
        cin >> a >> b;
        ile = 0;
        for (int j = a; j <= b; j++)
            if (T[j] == 1)
                ile++;
        cout << ile << endl;
    }
return 0;
}

Wydaje mi się że jest poprawnie

0

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

int main()
{
    ios_base::sync_with_stdio(0);
    int MAX_VAL, d;
    cin >> d;
    vector <int> przedzialy (d*2, 0);
    for (int i = 0; i < d * 2; i += 2){
        cin >> przedzialy[i] >> przedzialy[i+1];    //wcztywanie danych i wyznaczanie maksymalnej wartosci
        MAX_VAL = max(MAX_VAL, przedzialy[i+1]);
    }
    vector <int> sito(MAX_VAL+1, 0);
    vector <int> pref(MAX_VAL+2, 0);
    for (int i = 2; i * i <= MAX_VAL; i++){
        if (sito[i] == 0)
            for (int k = i*i; k <= MAX_VAL; k += i) //tworzenia sita Erasotenesa pod faktoryzacje
                if (sito[k] == 0)
                    sito[k] = i;
    }

    for (int p = 2; p * p * p <= MAX_VAL; p++){     //p to liczba pierwsza
        if (sito[p] == 0)
            pref[p * p * p + 1] = 1;                //zaznaczamy liczby doskonale w postaci p * p * p
    }

    for (int p = 2; p <= MAX_VAL; p++){
        if (sito[p] != 0 && sito[p / sito[p]] == 0 && sito[p] * sito[p] != p)
            pref[p+1] = 1;                          // zaznaczmy liczby doskonale w postaci p * licza pierwsza rozna od p
    }

    for (int i = 1; i <= MAX_VAL+1; i++)
        pref[i] += pref[i-1];

    for (int i = 0; i < d * 2; i+= 2){
        cout << pref[przedzialy[i+1]+1] - pref[przedzialy[i]] << endl;
    }
return 0;
}

Ten kod przechodzi wszystkie testy
EDIT: Teraz ten kod jest chyba taki jaki autor oczekiwał

Problem ze zrozumieniem i implementacja odpowiedzi do zadania

enedil napisał(a):

1 użytkowników online, w tym zalogowanych: 0, gości: 1

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami