Cod sursa(job #1125912)

Utilizator Athena99Anghel Anca Athena99 Data 26 februarie 2014 20:11:02
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

const int nmax= 2000000;

bool u[nmax+1];
int sol[nmax+1], prv[nmax+1], c[nmax+1];
queue <int> q;

inline int gcd( int x, int y ) {
    if ( y==0 ) {
        return x;
    }
    return gcd( y, x%y );
}

int main(  ) {
    int a, b, k= 0, m; fin>>a>>b;
    m= a*b/gcd(a, b);
    
    q.push(1);
    prv[1]= c[1]= 1;
    while ( !q.empty() ) {
        int x= q.front();
        q.pop();

        for ( int i= 0; i<=1; ++i ) {
            int y= (10*x+i)%m;
            if ( u[y]==0 ) {
                u[y]= 1, prv[y]= x, c[y]= i;
                q.push(y);
            }
        }
    }
    
    for ( int i= 0; i!=1; i= prv[i] ) {
        sol[++k]= c[i];
    }

    fout<<1;
    for ( int i= k; i>=1; --i ) {
        fout<<sol[i];
    }
    fout<<"\n";

    return 0;
}