Cod sursa(job #1827283)

Utilizator MoldovanMoldovan Moldovan Data 11 decembrie 2016 18:20:47
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>

using namespace std;
struct lee
{
    unsigned long long  nr;
    int rest;
};
int q[2000020];
int vct_tata[200020];
int adaug[2000020];
int retin[2000020],fr[2000020];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a, b , rest1,prod=1;

    scanf("%d %d",&a,&b);
    prod=a*b;
    while(b)
    {
        rest1=a%b;
        a=b;
        b=rest1;
    }
    prod/=a;

    if(prod==1)
    {
        printf("1");
        return 0;
    }
    int p =1, u =1,i;
    q[1]=1;
    vct_tata[1]=0;
    adaug[1]=1;
    while(p<=u)
    {
    rest1=q[p];
        for( i = 0 ; i <= 1;i++)
        {
            int m=(rest1*10+i)%prod;
            if(fr[m]==0)
            {

            q[++u]=m;
            vct_tata[u]=p;
            adaug[u]=i;
               fr[m]=1;
               if(m==0)
                {int l=p,cnt=1;
                retin[cnt]=i;
                while(l!=0)
                {
                    retin[++cnt]=adaug[l];
                    l=vct_tata[l];
                }
                for(int j = cnt;j>=1;j--)
                {
                    printf("%d",retin[j]);
                }
                return 0;
            }
            }
        }
        p++;
    }
    return 0;
}