Cod sursa(job #743724)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 5 mai 2012 17:24:47
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<iostream>
#include<fstream>
using namespace std;
char viz[2000010];
struct queue
{
	char c;
	int prev,r;
};
queue q[2000010];
char sol[2000010];
int main()
{
	int p,u,cmmdc,a,b,m,ca,cb,r1,lsol=0;
	ifstream f("multiplu.in");
	ofstream g("multiplu.out");
	f>>a>>b;
	f.close();
	ca=a;
	cb=b;
	while(cb!=0)
	{
		r1=ca%cb;
		ca=cb;
		cb=r1;
	}
	cmmdc=ca;
	m=a*b/cmmdc;
	p=1;u=1;
	q[1].r=1;q[1].prev=0;
	q[1].c=1;viz[1]=1;
	while(p<=u)
	{
		r1=(q[p].r*10)%m;
		if(viz[r1]==0)
		{
			viz[r1]++;
			u++;
			q[u].r=r1;
			q[u].prev=p;
			q[u].c=0;
			if(r1==0)
				break;
		}
		r1=(q[p].r*10+1)%m;
		if(viz[r1]==0)
		{
			viz[r1]++;
			u++;
			q[u].r=r1;
			q[u].prev=p;
			q[u].c=1;
			if(r1==0)
				break;
		}
		p++;
	}
	while(u>0)
	{
		sol[++lsol]=q[u].c;
		u=q[u].prev;
	}
	for(int i=lsol;i>0;i--)
		g<<(int)sol[i];
	g.close();
}