Cod sursa(job #391518)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 5 februarie 2010 20:16:51
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#define NMAX 2000010
int D[NMAX];
int v[NMAX], sol[NMAX], pre[NMAX];
bool anter[NMAX];
int m;
int cmmdc(int a,int b){
	if(a % b == 0)
		return b;
	return cmmdc(b, a%b);
}
void adauga(int x,int c){
	int p = ((long long) x*10 + c)%m;
	if(D[p]) return;
	D[p] = D[x] + 1;
	v[++v[0]] = p;
	pre[p] = x;
	anter[p] = c;
}
int main(){
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	int a, b;
	scanf("%d%d", &a, &b);
	m = a/cmmdc(a,b) * b;
	v[++v[0]] = 1;
	for(int i = 1; v[v[0]]; ++i){
		adauga(v[i], 0);
		if(!v[v[0]]) break;
		adauga(v[i], 1);
	}
	int x = 0;
	while(pre[x]){
		sol[++sol[0]] = anter[x];
		x = pre[x];
	}
	sol[++sol[0]] = 1;
	for(int i = sol[0]; i ; --i)
		printf("%d", sol[i]);
	printf("\n");
}