Cod sursa(job #2865201)

Utilizator daria_pDaria Popescu daria_p Data 8 martie 2022 16:41:09
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int a,b,nr,p,u,x,y,i,q[2000005],t[2000005];
bool f[2000005],v[2000005];
int cmmdc(int x,int y)
{
    while (y!=0)
    {
        int r=x%y;
        x=y;
        y=r;
    }
    return x;
}
void reconstituire(int p)
{
    if (p>0)
    {
        reconstituire(t[p]);
        fout<<v[p];
    }
}
int main()
{
    fin>>a>>b;
    nr=a/cmmdc(a,b)*b;
    p=u=1;
    f[1]=1;
    q[p]=1;
    v[p]=1;
    while (p<=u)
    {
        x=q[p];
        for (i=0; i<=1; i++)
        {
            y=(x*10+i)%nr;
            if (f[y]==0)
            {
                f[y]=1;
                q[++u]=y;
                t[u]=p;
                v[u]=i;
                if (y==0)
                {
                    reconstituire(u);
                    return 0;
                }
            }
        }
        p++;
    }
    return 0;
}