Cod sursa(job #1822421)

Utilizator alexradu04Radu Alexandru alexradu04 Data 4 decembrie 2016 21:11:42
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
using namespace std;
const int NMAX=2000000;
int q[NMAX+5],cif[NMAX+5],t[NMAX+5],sol[1000];
bool exista[NMAX+5];
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main ()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,i,p=0,u=1,mult,r,adaug=0,ok=0,nr;
    scanf("%d %d",&a,&b);
    mult=a*b/cmmdc(a,b);
    q[1]=exista[1]=cif[1]=1;
    while(p<=u && ok==0)
    {
        nr=q[++p];
        for(i=0; i<=1; i++)
        {
            r=(nr*10+i)%mult;
            if (exista[r]==0)
            {
                exista[r]=1;
                q[++u]=r;
                cif[u]=i;
                t[u]=p;
                if (r==0)
                {
                    while(1)
                    {
                        if(u)
                            sol[++adaug]=cif[u];
                        else
                        {
                            ok=1;
                            break;
                        }
                        u=t[u];
                    }
                }
            }
        }
    }
    for(i=adaug; i>=1; --i)
        printf("%d",sol[i]);
    return 0;
}