Cod sursa(job #119591)

Utilizator andrei.12Andrei Parvu andrei.12 Data 2 ianuarie 2008 10:15:40
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
#define lg 2000005
int n, m, x, y, r, fs[lg], st, end, sol[lg], s, i;
const int ct[] = {0, 1};
struct queue{
	int r, v, p;
};
queue q[lg];
int scm(int a, int b){
	int r;
	do{
		r = a % b;
		a = b;
		b = r;
	}
	while (b > 0);
	return a;
}
int main()
{
	freopen("multiplu.in", "rt", stdin);
	freopen("multiplu.out", "wt", stdout);
	
	scanf("%d%d", &n, &m);
	
	x = n*m / scm(n, m);
	//fprintf(stderr, "%d", x);
	
	q[1].v = 1, q[1].r = 1;
	st = 0, end = 1;
	
	while (st < end && !s){
		st ++;
		r = q[st].r;
		for (i = 0; i < 2 ; i ++){
			y = (r*10+ct[i]) % x;
			//fprintf(stderr, "la pasul %d avem restul %d din adaugarea lui %d in %d\n", st, y, ct[i], r);
			if (!fs[y]){
				q[++end].r = y;
				q[end].p = st;
				q[end].v = ct[i];
				fs[y] = 1;
			}
			if (!y){
				s = 1;
				break;
			}
		}
	}
	
	while (end){
		sol[++sol[0]] = q[end].v;
		end = q[end].p;
	}

	for (i = sol[0]; i; i --)
		printf("%d", sol[i]);
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}