Cod sursa(job #1418330)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 12 aprilie 2015 19:21:26
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#define HaHa 2000009

using namespace std;

bool f[HaHa];
int i,n,cif[HaHa],c[HaHa],t[HaHa],X,Y,m,p,u;

inline int cmmdc(int x,int y)
{
    int r=x%y;
    while(r)
    {
        x=y;y=r;r=x%y;
    }
    return y;
}
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);

    scanf("%d%d",&X,&Y);
    m=X*Y/cmmdc(X,Y);

    cif[1]=1;t[1]=0;
    c[1]=1;f[1]=1;

    p=u=1;
    while(p<=u)
    {
       if(!f[c[p]*10%m])
       {
           f[c[p]*10%m]=1;
           cif[++u]=0;
           t[u]=p;
           c[u]=c[p]*10%m;
           if(c[u]==0) break;
       }

       if(!f[ (c[p]*10+1)%m ])
       {
           f[ (c[p]*10+1)%m ]=1;
           cif[++u]=1;
           t[u]=p;
           c[u]=(c[p]*10+1)%m;
           if(c[u]==0) break;
       }
        ++p;
    }
    p=0;
    while(u!=0) f[++p]=cif[u], u=t[u];

    for(i=p;i>=1;--i) printf("%d",f[i]);
    printf("\n");
    return 0;
}