Cod sursa(job #2964671)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 13 ianuarie 2023 16:26:25
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;



const int NMAX = 2e6 + 2;

int coada[NMAX],from[NMAX],cif[NMAX];

void afis(int ind)
{
    if(!ind)
        return;

    afis(from[ind]);
    if(cif[ind]) putchar('1');
    else         putchar('0');
}

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);

    int a,b; cin >> a >> b;
    int lcm = a * b / __gcd(a,b);

    vector<bool> avem(lcm + 1,0);
    queue<int> q;

    coada[1] = 1;
    avem[1] = 1;
    cif[1] = 1;


    int st = 1,dr = 1;
    for(;;)
        {
            int rest = coada[st++];
            if(!avem[(rest * 10) % lcm])
                {
                    int p = rest * 10;
                    p %= lcm;
                    avem[p] = 1;
                    coada[++dr] = p;
                    from[dr] = st - 1;
                    if(!p)
                        break;
                }

            if(!avem[(rest * 10 + 1) % lcm])
                {
                    int p = rest * 10 + 1;
                    p %= lcm;
                    avem[p] = 1;
                    cif[++dr] = 1;
                    coada[dr] = p;
                    from[dr] = st - 1;

                    if(!p)
                        break;
                }

        }

    afis(dr);
}