Ułamek okresowy

Witam!
Mam za zadanie wyznaczenie okresu ułamka w postaci p / q. Okres może mieć długość do tysiąca cyfr. p i q są mniejsze od dwóch miliardów. Ułamek może nie mieć okresu, wtedy trzeba wypisać "NIE".

Nie mam pojęcia jak się za to zabrać i nie mogę nic na ten temat wygooglować. Ma ktoś jakiś pomysł?

pozdrawiam
piternet

zakładam, że p<q oraz, że p i q są względnie pierwsze (NWD(p,q)=1).

Zadanie jest banalnie proste, zrób dzielenie pisemne np 2/7 i zobacz co się dzieje.
Kiedy w pisemnym dzieleniu stwierdzisz, że masz okresowość?
Jeśli reszta z dzielenia kolejnego słupka, będzie taka sama jak reszta z dzielenia jednego z poprzednich słupków.

Nie wydaje mi się, żeby to było dobrym sposobem.
Mam dla przykładu okres 0, (5443664564). To że powtórzy mi się 5 nie oznacza, że już mam okres.

Nie zrozumiałeś. Napisał "reszta z dzielenia", a nie cyfra wyniku. Reszta to to co dostajesz w dzieleniu pisemnym na dole jako wynik operacji odejmowania.

dam kod bo mam dobry humor i problem mi się podoba:

string ulamekOkresowy(unsigned int p, unsigned int q) {
    string result;
    ostringstream out(result);
    out << p/q << '.';
    p%=q;
    map<unsigned int, int> oldRemainders;

    while(p!=0) {
        int strPos = result.length();
        p = p*10;
        out << p/q;
        p = p%q;
        if (oldRemainders.find(p)!=oldRemainders.end()) {
             out << ')';
             result.insert(oldRemainders[p], "(");
             break;
        }
        oldRemainders[p] = strPos;
    }

    return result;
}

////edycja postu, poprzednia treść nieważna

edit
mam pytanie, bo zmodyfikowałem mój kod, aby byl zgodny z zadaniem(N przypadków testowych, wypisywanie NIE gdy nie ma okresu) i coś zaczęło się psuć.
KOD:

#include <iostream>
#include <string>

using namespace std;

int ilezer(int a)
{
    int e = 0;
    while(a > 1)
    {
        e++;
        a/=10;
    }
    int wy = 10;
    while(e--)
        wy*=10;
    return wy;
}

int main()
{
    int N;
    cin >> N;
    while(N--)
    {
        int p, q, licz = 0;
        cin >> p >> q;
        if(p > q)
            p-=q;
        string okres;
        bool czy = false;
        const int mnoznik = ilezer(q);
        long long reszta = p * mnoznik;
        long long resztapocz = reszta;
        while(true)
        {
            licz++;
            int ile = reszta / q;
            reszta%=q;
            reszta*=mnoznik;
            //cout << ile; chce to miec w stringu
            char wrzuc = static_cast<char>(ile) + '0';
            okres.push_back(wrzuc);
            if(reszta == 0)
            {
                cout << "NIE";
                return 0;
            }
            if(reszta == resztapocz)
                break;
        }
        cout << okres << "\n";
    }
    return 0;
}

Przykład testowy:
4 // liczba przypadkow
1 11 //p jest pierwsze, po nim q
1 6
1 30
5 4

No i odpowiedz do tego:
09
6
3
NIE

Mój program po wpisaniu 1 11 wypisuje 9 (bez zera ;/), ale dla testu 1 6 już się zawiesza. Co jest źle?

Tu jest poprawka, nie mam pod ręką kompilatora więc sprawdź sam:

string ulamekOkresowy(unsigned int p, unsigned int q) {
    ostringstream out;
    out << p/q << '.';
    p%=q;
    map<unsigned int, int> oldRemainders;
 
    while(p!=0) {
        oldRemainders[p] = out.tellp();
        p = p*10;
        out << p/q;
        p%=q;

        if (oldRemainders.find(p)!=oldRemainders.end()) {
             out << ')';
             return out.str().insert(oldRemainders[p], "(");
        }
    }

    return out.str();
}

Rozumiesz w ogóle na czym polega mój algorytm?
Po co ty masz tą funkcję ilezer (nazwa jest bez sensu).

poza tym zadanie okazało się trudniejsze niż myślałem. Chodzi mi o to, że np. ułamek 1/6 ma okres (6), ale przed okresem ma jedynkę, tj. 1/ 6 = 0.1(6). W przykładzie do zadania jest właśnie test 1 6 i odpowiedź to 6. Twój program podaje 16. Tak samo dla testu 1 30, przed okresem wynoszącym (3) jest zero, a twój program traktuje je jak okres.

Jak najprościej możnaby przystosować program do takiej sytuacji?

wykonujesz dzielenia, zapisujesz reszty i gdy po raz pierwszy powtórzy ci się reszta, oznacza to, że segment od pierwszego wystąpienia reszty do pierwszego powtórzenia jest okresem.