"Liczby specjalne"

Question

Witam.

Mam problem z tym zadaniem Treść zadania

Mój kod:

#include <iostream>

using namespace std;

int main()
{
    long long N,licznik=0;
    cin >> N;
    if(N>=1)
    {
        for(int i=0; i<=N; i=i+17)
        {
            if(i%10==7)
                licznik++;
        }
    }
    cout << licznik;
    return 0;
}

Jednak limit czasu jest przekroczony - tu jest problem, nie wiem jak go rozwiązać.

Za wszelkie wskazówki, porady będę wdzięczny.

Answer 1

w wymaganiach jest 10^18 więc o ile pamiętam to jest 1 000 000 000 000 000 000. Nie dziw że przekracza czas jeśli tak to robisz.

Comments

Masz jakiś pomysł jak to inaczej zrobić?

Answer 2

1 <= N <=10^18 - Polecam uzyc tablicy char

Cecha podzielności przez 17

Cyfrę jedności pomnóż przez 5 i odejmij od liczby utworzonej z pozostałych cyfr.Jeżeli wynik dzieli się przez 17 lub jest zerem to liczba początkowa jest podzielna przez 17.(wynik może być ujemny)

Przykład:Dla 123 mamy 12-15=-3 a więc liczba 123 nie jest podzielna przez 17

Petla mozesz zaczac juz od 17, zaoszczedzisz troche czasu.

Comments

Czy to na pewno szybszy sposób ?

---

#include <iostream>
int funkcja(long long n,long long &licz,long long i)
{
    if(i<n)
    {
        if(i%10==7)++licz;
        funkcja(n,licz,i+17);
    }
    return licz;
}
int main()
{
    long long N,licznik=0,i=17;
    std::cin >> N;
    std::cout << funkcja(N,licznik,i);
    return 0;
}

Powinno dzialac

Answer 3

Powinno być całkiem szybko. Przerobienie na ew. odpowiedź do zadania to już Twoja sprawa :-)

#include <iostream>
#include <string>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <set>

// Mały Bonus... jak będziesz chciał wyjść poza zakres POD'ów 
// i uzyskać 100% punktacji, ta funkcja może być punktem startu...
bool check17DivideEnded7(const std::string& value) {
    // Sprawdzenie czy kończy się na 7. Od razu obliczenie do 
    // sprawdzenia warunku podzielności przez 17'cie.
    int lastValue = (*value.crbegin() - '0') * 5;
    if(35 != lastValue) {
        return false;
    }
    // Sumuje cyfry reprezentowane w string'u bez ostatniej.
    int sum = std::accumulate(value.cbegin(), value.cend() - 1, '0',
            [](char a, char b) {
                return a + b - '0';
    }) - '0' - lastValue;

    return ! (sum % 17 % 10);
}

std::set<int> findValues(int value) {
    constexpr static int gcd17and7 = 17 * 7;
    std::set<int> values;
    int computeValue;
    int i = 0;
    int correctionTable[] = {1, 4, 7, 0, 3, 6, 9, 2, 5, 8};

    while((computeValue = (i * gcd17and7 + correctionTable[i % 10] * 17)) < value) {
        ++i;
        values.insert(computeValue);
    }

    return values; 
}

void showSet(const std::set<int>& values) {
    std::copy(values.cbegin(), values.cend(),
            std::ostream_iterator<int>(std::cout, ", "));
}

int main() {
    int value;
    std::cout << "Podaj liczbę: ";
    std::cin >> value;

    auto values = findValues(value);
    std::cout << "Poniżej tej wartości jest " << values.size()
        << " liczb spełniających krtreria.\n";
    std::cout << "Są to: ";
    showSet(values);
    std::cout << std::endl;
}

Comments

Dziękuję pięknie :)

Na pewno przejrzę kod, ale nie oddam go jako mój, żeby mieć zadanie zaliczone, to nie jest mój poziom (mam nadzieję, że jeszcze nie...).

---

Oczywiście że nie oddawaj jako swój! Nie po to go pisałem i dlatego nie trzymałem się ściśle wymagań zadania. Masz tu zastosowanie zbioru do usunięcia duplikatów, tablicę ze współczynnikami która pozwala zejść do dość niskiej złożoności obliczeniowej (ale nie teoretycznie osiągalnej) oraz stosowanie algorytmów wraz z iteratorami.

(zdradzę że w zadaniu wcale nie należy szukać tych liczb tylko znaleźć formułę obliczeń ile ich jest).