Cod sursa(job #1962294)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 11 aprilie 2017 18:04:29
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <cstdio>

using namespace std;
const int NMAX=2000000;
int cmmmc(int a,int b)
{
    int p=a*b;
    while (a!=b)  {
        if (a>b)
           a=a-b;
        else
           b=b-a;
    }
    int r=p/a;
    return r;
}
struct MULTIPLU
{
    int c,r,t;
};
MULTIPLU q[NMAX+5];
bool fr[NMAX+5],sol[NMAX+5];

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,r,k,i;
    scanf("%d%d", &a, &b);
    int p,u,m=cmmmc(a,b);
    p=1;u=1;
    MULTIPLU temp;
    q[p].c=1;q[p].r=1;q[p].t=0;
    temp.c=1;temp.r=1;temp.t=0;fr[q[p].r]=1;
    while(p<=u)
    {
        r=(q[p].r*10+0)%m;
        if(fr[r]==0)
        {
            u++;
            fr[r]=1;
            q[u].c=0;q[u].r=r;q[u].t=p;
            if(r==0)
                break;
        }
        r=(q[p].r*10+1)%m;
        if(fr[r]==0)
        {
            u++;
            fr[r]=1;
            q[u].c=1;q[u].r=r;q[u].t=p;
            if(r==0)
                break;
        }
        p++;
    }
    k=0;
    while(u)
    {
        sol[++k]=q[u].c;
        u=q[u].t;
    }
    for(i=k;i>=1;i--)
    {
        printf("%d", sol[i]);
    }
    return 0;
}