Cod sursa(job #2000606)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 14 iulie 2017 11:31:20
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<fstream>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
int rez[2000001],a,b,x,y,l[2000001],t[2000001],v[2000001],st,dr,n,r,mod,i,hz[2000001];
void find_solution( int x ){
    if( t[x] == -1 ){
        rez[++n] = l[x];
    }
    else{
        rez[++n] = l[x];
        find_solution( t[x] );
    }
}
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 ++ ){
        if( hz[((v[st]*10 + 1) % mod)] == 0 ){
            dr++;
            v[dr] = (v[st]*10 + 1) % mod;
            t[dr] = st;
            l[dr] = 1;
            hz[((v[st]*10 + 1) % mod)] = 1 ;
            if( v[dr] == 0 ){
                find_solution( dr );
                break;
            }
        }
        if( hz[((v[st]*10) %  mod)] == 0 ){
            dr++;
            v[dr] = (v[st]*10) %  mod;
            t[dr] = st;
            l[dr] = 0;
            hz[((v[st]*10) %  mod)] = 1;
            if( v[dr] == 0 ){
                find_solution( dr );
                break;
            }
        }
    }
    for( i = n; i >= 1; i -- ){
        out<<rez[i];
    }
    return 0;
}