Cod sursa(job #552094)

Utilizator MKLOLDragos Ristache MKLOL Data 11 martie 2011 17:13:13
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<vector>
#include<bitset>
#include<algorithm>
#include<iostream>
using namespace std;

struct cel
{
        int pred,val,mod;
} coad[2020200];

int cmmdc(int a,int b)
{
    if(b==0)
    return a;
    return cmmdc(b,a%b);
}
int A,B,M,st,dr;
bitset<2020200> mod;
void afis(cel a)
{
    if(a.pred!=-1)
    {
        afis(coad[a.pred]);
    }
    printf("%d",a.val);
}
int main()
{
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
scanf("%d%d",&A,&B);

    M=A*B/cmmdc(A,B);
    st=0;dr=1;

    mod[1%M]=1;
   // printf("%d\n",M);
    coad[0].pred=-1;
    coad[0].val=1;
    coad[0].mod=1%M;

    while(st<=dr)
    {
    //    printf("%d %d\n",st,dr);
        if(coad[st].mod==0)
        {
            afis(coad[st]);
            return 0;
        }
        if(!mod[(coad[st].mod*10)%M])
        {
            mod[(coad[st].mod*10)%M]=1;
            coad[dr].pred=st;
            coad[dr].mod=(coad[st].mod*10)%M;
            coad[dr].val=0;
            ++dr;
        }
        if(!mod[(coad[st].mod*10+1)%M])
        {
            mod[(coad[st].mod*10+1)%M]=1;
            coad[dr].pred=st;
            coad[dr].mod=(coad[st].mod*10+1)%M;
            coad[dr].val=1;
            ++dr;
        }

        ++st;
    }


}