Cod sursa(job #633712)

Utilizator dariusdariusMarian Darius dariusdarius Data 14 noiembrie 2011 16:45:20
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#include<queue>
#define NMAX 2000000
using namespace std;
struct POINT {char c;int r,t;};
POINT q[2000009];
bool viz[2000009];
int cmmmc(int a,int b)
{
	int ca,r,cb;
	ca=a;cb=b;
	while(b)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return ca*cb/a;
}
int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	int a,b,m;
	scanf("%d%d",&a,&b);
	m=cmmmc(a,b);
	int p=1,u=1,r;
	q[p].c=1;q[p].r=1;
	q[p].t=0;
	viz[1]=1;
	while(p<=u)
	{
		r=(10*q[p].r)%m;
		if(!viz[r])
		{viz[r]=1;q[++u].c=0;q[u].r=r;q[u].t=p;}
		if(r==0)
		{
			while(q[u].t!=0)
			{
				printf("%d",q[u].c);
				u=q[u].t;
			}
			printf("%d",q[u].c);
			break;
		}
		r=(r+1)%m;
		if(!viz[r])
		{viz[r]=1;q[++u].c=1;q[u].r=r;q[u].t=p;}
		if(r==0)
		{
			while(q[u].t!=0)
			{
				printf("%d",q[u].c);
				u=q[u].t;
			}
			printf("%d",q[u].c);
			break;
		}
		p++;
	}
	return 0;
}