Cod sursa(job #1414279)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 2 aprilie 2015 14:47:09
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
const int MAX=2000000;
int q[MAX];
int father[MAX+1];
bool vis[MAX+1];
bool c[MAX+1];
int res[MAX+1];
int a,b;
int main(){
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a;
    scanf("%d%d",&a,&b);
    int ca=a,cb=b;
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    a=ca*cb/a;
    int ql=1,qr=1;
    q[1]=1;
    c[1]=1;
    vis[1]=true;
    while(true){
        int r=(q[ql++]*10)%a;
        if(!vis[r]){
            q[++qr]=r;
            vis[r]=true;
            c[qr]=0;
            father[qr]=ql-1;
            if(!q[qr])
                break;
        }
        r=(r+1)%a;
        if(!vis[r]){
            q[++qr]=r;
            c[qr]=1;
            father[qr]=ql-1;
            vis[r]=true;
            if(!q[qr])
                break;
        }
    }
    int pos=qr;
    int k=0;
    while(pos){
        res[++k]=c[pos];
        pos=father[pos];
    }
    for(int i=k;i>=1;i--)
        printf("%d",res[i]);
    return 0;
}