Cod sursa(job #1540275)
Utilizator | Vlad 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;
}