Cod sursa(job #2774751)

Utilizator Emilia23Dobra Emilia Emilia23 Data 12 septembrie 2021 17:41:31
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("multiplu.in");
ofstream g("multiplu.out");

const int SIZE = 2000005;

int from[SIZE],sol[SIZE],c;

queue <int> q;

int cmmmc(int x,int y)
{
    int r,p=x*y;
    while(y != 0)
    {
        r = x % y;
        x = y;
        y = r;
    }
    return p/x;
}

void afis(int n)
{
    if(n!=-1)
    {
        afis(from[n]);

        if((from[n]*10)%c == n)g<<0;
        else g<<1;
    }
}

int main()
{
   int a,b,k=0,n,m;

    f>>a>>b;
    c=cmmmc(a,b);

    if(c==1)
    {
        g<<1;
        return 0;
    }

    q.push(1);
    from[1]=-1;

    while(1==1)
    {
        //luam primul rest
        m=q.front();
        q.pop();

        n=(m*10)%c;

        //verificam daca mai apare noul rest (cazul cu *10 )
        if(from[n]==0)
        {
            from[n]=m;
            if(!n)break;
            q.push(n);
        }

         n=(m*10+1)%c;

        //verificam daca mai apare noul rest (cazul cu *10+1 )
        if(from[n]==0)
        {
            from[n]=m;
            if(!n)break;
            q.push(n);
        }
    }

    //afisare
    afis(0);

    return 0;

}