Cod sursa(job #462681)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 12 iunie 2010 16:57:35
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#define DIM 2000002

using namespace std;

int c[DIM],v[DIM],cif[DIM],t[DIM],p,u,i,a,b,x,y,r,vec,m;

ifstream f("multiplu.in");
ofstream g("multiplu.out");

void reconstitue(int u)
{
	if (u!=0) {
		reconstitue(t[u]);
		g<<cif[u];
	}
}
	
	
int main()
{

	f>>a>>b;
	
	x=a;y=b;r=a%b;
	while (r>0)
	{
		x=y;
		y=r;
		r=x%y;
	}
	m=a*b/y;
	
	c[1]=1;v[1]=1;p=u=1;cif[1]=1;
	
	while(p<=u)
	{
		for (i=0;i<=1;i++)
		{
			vec=(10*c[p]+i)%m;
			if (v[vec]==0)
			{
				c[++u]=vec;
				v[vec]=1;
				cif[u]=i;t[u]=p;
			}
			if (vec==0)
			{
				reconstitue(u);
				u = p+1;
				break;
			}
		}
		++p;
	}
	f.close();
	g.close();
	return 0;
}