Cod sursa(job #116577)

Utilizator VmanDuta Vlad Vman Data 18 decembrie 2007 22:43:02
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
using namespace std;
#include <stdio.h>

#define Mmax 2000002

int A,B,D,M;
int h[Mmax],q[Mmax],last[Mmax];
char cif[Mmax];

int cmmdc(int A,int B)
{
 int r;
 while (B)
       {
        r=A%B;
        A=B;
        B=r;
       }
 return A;
}

void afisaza(int i)
{
 if (i!=1) afisaza(last[i]);
 printf("%d",cif[i]);
}

void solve()
{
 int st,dr,r;
 q[st=dr=1]=1;
 h[1]=1;
 cif[1]=1;
 while ((st<=dr)&&(h[0]==0))
       {
        r=(q[st]*10)%M;
        if (h[r]==0)
           {
            q[++dr]=r;
            last[dr]=st;
            cif[dr]=0;
            h[r]=dr;
           }
        r=(q[st]*10+1)%M;
        if (h[r]==0)
           {
            q[++dr]=r;
            last[dr]=st;
            cif[dr]=1;
            h[r]=dr;
           }
        ++st;
       }
 afisaza(h[0]);
}

int main()
{
 freopen("multiplu.in","r",stdin);
 freopen("multiplu.out","w",stdout);
 scanf("%d %d",&A,&B);
 D=cmmdc(A,B);
 M=A*B/D;
 if (M>1) solve();
    else printf("%d",1);
 fclose(stdin);
 fclose(stdout);
 return 0;
}