Zadanie Gra w dzielniki OI, sito Eratostenesa

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/Nuzr3WcSxrZWjKLJuI9s74Jn/site/?key=statement

Napisałem kod, który wchodzi na 80pkt, w 2 testach daje przekroczenie limitu czasu, a w jednym niewłaściwy argument funkcji zgaduj (wydaje mi się, to dziwne bo kod jest wmiarę prosty). Szukam wszystkie liczby pierwsze i potem sprawdzam poprostu przez co dzieli się. Tak jakby faktoryzuje nie znając jej.

Ma ktoś pomysł, gdzie jest błąd?

#include <iostream>
#include <vector>
#include "maja.h"
#include <cmath>

using namespace std;
typedef long long ll;

int n = 0, wyn = 1;
bool sito[1000001] = {false};
vector<int> P;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for (int i = 2; i <= 1e6; ++i)
    {
        if (sito[i] == false)
        {
            P.push_back(i);
            if (i <= 1e3)
                for (int j = i*i; j <= 1e6; j += i)
                    sito[j] = true;
        }
    }

    while(true)
    {
        n = gramy_dalej();
        if (n == 0)
            break;
        wyn = 1;
        for (int i = 0; i < P.size(); ++i)
        {
            if (P[i] > n)
                break;
            if (czy_podzielna_przez(P[i]) == 1)
            {
                wyn *= P[i];
                int x = P[i] * P[i];
                if (P[i] <= sqrt(n)+1)
                {
                    while(true)
                    {
                        if (x > n)
                            break;
                        if (czy_podzielna_przez(x) == 1)
                        {
                            wyn *= P[i];
                            x *= P[i];
                            if ((ll)x * (ll)x > n)
                                break;
                        }
                        else
                            break;
                    }
                }
            }
        }
        zgaduj(wyn);
    }

    return 0;
}

Z góry dziękuję za pomoc i poświęcony czas!

Comments

Myśłalem, ze mówisz o tym zadaniu :) Ono była całkiem trudne i korzystało z liczenia wartości oczekiwanej, ale to tutaj wydaje się łatwiejsze

---

to zadanie wydaje, się być mega trudne(te z XXVI OI).

---

@pasjonat_algorytmiki, Zadanie jest dziwne, bo nie rostrzyga jak postąpić gdy jeden czynnik występuje wielokrotnie w rozkładzie szukanej liczby

---

Rozstrzyga. Zawsze musisz zrobić tak, żeby mieć pewność, że zgadłeś liczbę, dlatego jest while zaczynający się 46 linii. Sprawdzam czy jest podzielne przez P1^1 jak jest to sprawdzam P1^2, jak tak to sprawdzam P1^3......

P1, to jakaś dowolna liczba pierwsza. Jeśli w jakimś momencie nie będzie podzielna przez P1^x, to kończe.

---

https://godbolt.org/z/enbxYExaz

Answer 1

Wystarczy przerywać pętle gdy:

wyn * P[i] > n

 

Comments

No wsm to takie oczywiste było......

Wystarczy if-a z 38 linii zamienić na np:

if (P[i] > n or wyn * P[i] > n)

Korzystając z okazji, znasz jeszcze jakieś fajne zadanka na sito Eratostenesa / faktoryzacje / rozklad na dzielniki, i takie inne rzeczy teorioliczbowe, oprócz tego i tej odległości co jakiś czas temu wrzuciłem na forum?

Dzięki!

---

Np.

Liczby kompletne

Gra w dzielniki :)

A inne zadania na teorię liczb to np.

Podzielność

Rozkład Fibonacciego

Co do tego ostatniego to warto nauczyć się dowód, dlaczego rozwiązanie działa (ja go akurat nigdy nie umiałem )

Takie fajne zadanie które widziałem kiedyś na konkursie Fraktal na spoju: policzyć ostatnią niezerową cyfrę silnii zapisanej w podanym systemie liczbowym