Cod sursa(job #393705)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 9 februarie 2010 20:43:46
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>

#define MAX (1<<21)

int cmmdc(int a, int b);

int a, b, m, rest[MAX], pred[MAX], p, u, poz, i, n; 
bool obt[MAX], cif[MAX], nr[MAX];

int main()
{
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	scanf("%d%d", &a, &b);
	m=(a*b)/cmmdc(a,b);
	if (m==1)
		printf("1");
	else
	{
		rest[u]=1;
		cif[u]=1;
		obt[1]=1;
		while ((p<=u)&&(!obt[0]))
		{
			if (!obt[(rest[p]*10)%m])
			{
				u++;
				rest[u]=(rest[p]*10)%m;
				obt[(rest[p]*10)%m]=1;
				cif[u]=0;
		    pred[u]=p;
				if (rest[u]==0)
					poz=u;
			}//if
			if (!obt[(rest[p]*10+1)%m])
			{
				u++;
				rest[u]=(rest[p]*10+1)%m;
				obt[(rest[p]*10+1)%m]=1;				
				cif[u]=1;
		    pred[u]=p;
				if (rest[u]==0)
					poz=u;				
			}//if			
			p++;
		}//while	
		while (poz!=0)
		{
			nr[n++]=cif[poz];
			poz=pred[poz];
		};
		nr[n]=1;
		for (i=n; i>=0; i--)
			printf("%d", nr[i]);
	}//else
	return 0;
}//mian

int cmmdc(int a, int b)
{
	if (b==0)
		return a;
	return cmmdc(b, a%b);
}//cmmdc