Cod sursa(job #633713)

Utilizator lam99Tran Bach Lam lam99 Data 14 noiembrie 2011 16:48:03
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <stack>
#include <queue>
#define NMAX 20000005
using namespace std;
int cmmdc(int a1,int b1)
{
    int rr;
    while(b1)
    {
        rr=a1%b1;
        a1=b1;
        b1=rr;
    }
    return a1;
}
struct lam
{
    bool c;
    int r,t;
};
stack <bool> st;
int a,b,m,p,u,r,r1,c;
lam q[NMAX];
bool viz[NMAX];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d%d",&a,&b);
    m=cmmdc(a,b);
    m=a*b/m;
    p=u=1;
    q[p].c=1;
    q[p].r=1;
    q[p].t=0;
    viz[1]=1;
    while(p<=u)
    {
        c=0;
        r1=(q[p].r*10+c)%m;
        if(!viz[r1])
        {
            q[++u].c=c;
            q[u].r=r1;
            q[u].t=p;
            viz[r1]++;
            if(r1==0)
            {
                break;
            }
        }
        c=1;
        r1=(q[p].r*10+c)%m;
        if(!viz[r1])
        {
            q[++u].c=c;
            q[u].r=r1;
            q[u].t=p;
            viz[r1]++;
            if(r1==0)
            {
                break;
            }
        }

        p++;
    }
    while(u)
    {
        st.push(q[u].c);
        u=q[u].t;
    }
    while(!st.empty())
    {
        printf("%d",st.top());
        st.pop();

    }
}