Cod sursa(job #1414278)

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