Cod sursa(job #2000861)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 14 iulie 2017 21:33:50
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
int a,b,x,y,l[2000001],ok,t[2000001],v[2000001],st,dr,n,r,alfa,mod,i,hz[2000001],k;
char rez[2000001];
int main(){
    in >> a >> b;
    x = a; y = b;
    while( b > 0 ){
        r = a % b;
        a = b;
        b = r;
    }
    mod = x*y / a;
    v[1] = 1;
    l[1] = 1;
    t[1] = -1;
    hz[1] = 1;
    for( st = 1, dr = 1; st <= dr; st ++ ){
        for (i = 0; i <= 1; i ++){
            k = (v[st]*10 + i) % mod;
            if( hz[k] == 0 ){
                dr++;
                v[dr] = k;
                t[dr] = st;
                l[dr] = i;
                hz[k] = 1 ;
                if( v[dr] == 0 ){
                    alfa = dr;
                    ok = 1;
                    break;}
            }
        }
        if( ok == 1){
            break;
        }
    }
    while( alfa != -1 ){
        rez[++n] = l[alfa] + 48;
        alfa = t[alfa];
    }
    for( i = 0; i <= n/2; i ++ ){
        swap( rez[i],rez[n-i+1]);
    }
    out<<rez+1;
    return 0;
}