Cod sursa(job #1540282)

Utilizator IoanZioan zahiu IoanZ Data 2 decembrie 2015 16:07:06
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>

using namespace std;

struct MULTIPLU
{
    int c,r,t;
}q[2000000];

bool viz[2000000],nr[2000000];

int cmmdc(int a,int b)
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,u,p,i;
    scanf("%d%d",&a,&b);
    if (a==1 && b==1){
        printf("1\n");
        return 0;
    }
    m=a*b/cmmdc(a,b);
    q[1].c=q[1].r=viz[1]=1;
    p=u=1;
    while(p<=u)
    {
        if (viz[(q[p].r*10)%m]==0)
        {
            u++;
            viz[(q[p].r*10)%m]=1;
            q[u].r=(q[p].r*10)%m;
            q[u].c=0;
            q[u].t=p;
            if (q[u].r==0)
                break;
        }
        if (viz[(q[p].r*10+1)%m]==0)
        {
            u++;
            viz[(q[p].r*10+1)%m]=1;
            q[u].r=(q[p].r*10+1)%m;
            q[u].c=1;
            q[u].t=p;
            if (q[u].r==0)
                break;
        }
        p++;
    }
    i=0;
    while (u)
    {
        nr[++i]=q[u].c;
        u=q[u].t;

    }
    while (i)
    {
        printf("%hd",nr[i]);
        i--;
    }
    return 0;
}