Cod sursa(job #2149366)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 2 martie 2018 15:48:11
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>

using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
int cmmdc (int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int cmmmc(int a,int b)
{
    return a*b/cmmdc(a,b);
}
int l[2000001],t[2000001],v[2000001],hz[2000001];
char rez[2000001];
int main()
{
    int a,b,st,dr,i,mod,ok=0,n=0,r,alfa,k;
    in>>a>>b;
    mod=cmmmc(a,b);
    v[1] = 1;
    l[1] = 1;
    t[1] = -1;
    hz[1] = 1;
    st=1;
    dr=1;
    while(st<=dr)
    {
        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;
        }
        st++;
    }
    while( alfa != -1 )
    {
        n++;
        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;
}