Cod sursa(job #1540275)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 2 decembrie 2015 16:01:48
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
bool viz[2000000], nr[2000000];
struct MULTIPLU
{
    int c;
    int r;
    int t;
} q[2000000];
int cmmdc( int a, int b )
{
    int r;
    while( b )
        r=a%b, a=b, b=r;
    return a;
}
int main()
{
    freopen( "multiplu.in", "r", stdin );
    freopen( "multiplu.out", "w", stdout );
    int a, b, m, u, p, i=0;
    scanf( "%d%d", &a, &b );
    if( a==1 && b==1 )
        printf( "1" );
    else
    {
        m=a*b/cmmdc(a,b);
        q[1].c=q[1].r=viz[1]=1;
        q[1].t=0;
        p=u=1;
        while( p<=u )
        {
            if( !viz[(q[p].r*10)%m] )
            {
                u++;
                viz[(q[p].r*10)%m]=1;
                q[u].r=((q[p].r%m)*10)%m;
                q[u].t=p;
                if( viz[0] )
                    break;
            }

            if( !viz[(q[p].r*10+1)%m] )
            {
                u++;
                viz[(q[p].r*10+1)%m]=1;
                q[u].r=(q[p].r*10+1)%m;
                q[u].t=p;
                q[u].c=1;
                if( viz[0] )
                    break;
            }

            p++;
        }
        while( u )
        {
            nr[++i]=q[u].c;
            u=q[u].t;
        }
        while( i )
        {
            printf( "%d", nr[i] );
            i--;
        }
    }
    return 0;
}