Cod sursa(job #1540267)

Utilizator GhiciCineRazvan Dumitriu GhiciCine Data 2 decembrie 2015 15:54:45
Problema Multiplu Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>

struct MULTIPLU {
	char c;
	int r, t;
} q[2000005];

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 );
}

char viz[2000001];
char v[2000001];
int main(){
	freopen( "multiplu.in", "r", stdin );
	freopen( "multiplu.out", "w", stdout );
	int a, b, M, p, u, i;
	
	scanf( "%d%d", &a, &b );
	M = cmmmc( a, b );
	q[1].c = 1;
	q[1].r = 1;
	q[1].t = 0;
	p = u = 1;
	while( p <= u ) {
		if( viz[ ( q[p].r * 10 + 0 ) % M ] == 0 ) {
			u++;
			q[u].c = 0;
			q[u].r = ( q[p].r * 10 + 0 ) % M;
			q[u].t = p;
			viz[q[u].r] = 1;
			if( q[u].r == 0 )
				break;
		}
		if( viz[ ( q[p].r * 10 + 1 ) % M ] == 0 ) {
			u++;
			q[u].c = 1;
			q[u].r = ( q[p].r * 10 + 1 ) % M;
			q[u].t = p;
			viz[q[u].r] = 1;
			if( q[u].r == 0 )
				break;
		}
		p++;
	}
	i = 1;
	for( ; u != 0; u = q[u].t ) {
		v[i] = q[u].c;
		i++;
	}
	i--;
	for( ; i >= 1; i-- )
		printf( "%d", v[i] );
	return 0;
}