Cod sursa(job #1540280)

Utilizator bogdi1bogdan bancuta bogdi1 Data 2 decembrie 2015 16:05:04
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>

using namespace std;
struct Multiplu
{
    bool c;
    int r;
    int t;
} q[2000005];
int cmmdc(int a, int b)
{
    int rr;
    while(b){
        rr=a%b;
        a=b;
        b=rr;
    }
    return a;
}
bool v[2000005];
bool viz[2000005];
int main()
{   freopen("multiplu.in", "r",stdin);
    freopen("multiplu.out", "w",stdout);
    int a,b,m,p,u,i,j;
    scanf("%d%d", &a, &b);
    m=a*b/cmmdc(a,b);
    q[1].c=1;
    q[1].r=1;
    q[1].t=0;
    p=u=1;
    viz[1]=1;
    while(p<=u){
        if(viz[(q[p].r*10+0)%m]==0){
            q[++u].r=(q[p].r*10+0)%m;
            q[u].c=0;
            q[u].t=p;
            viz[q[u].r]=1;

        if(viz[0]==1)
            break;
        }
        if(viz[(q[p].r*10+1)%m]==0){
            q[++u].r=(q[p].r*10+1)%m;
            q[u].c=1;
            q[u].t=p;
            viz[q[u].r]=1;
        if(viz[0]==1)
            break;
        }
        p++;
    }
    i=1;
    while(q[u].t!=0){
        v[i]=q[u].c;
        i++;
        u=q[u].t;
    }
    v[i]=q[1].c;
    for(j=i; j>0; j--)
        printf("%d", v[j]);
    return 0;
}