Cod sursa(job #355030)

Utilizator APOCALYPTODragos APOCALYPTO Data 10 octombrie 2009 00:21:42
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream.h>
#include<iostream.h>
#include <stdlib.h>
const int M = (1<<22);

int a,b,m,up[M],q[M],*r=new int[M];
short int cif[M];
ofstream fout("multiplu.out");
long cmmdc(long a,long b)
{
int r;
while(b)
{
r=a%b;
a=b;
b=r;
}
return a;
}
void afara(int k)
{if(k!=1)
      afara(up[k]);
     fout<<cif[k];
}
int main()
{int k=1,dimq=0,x,y,i,c;
    ifstream f("multiplu.in");
f>>a>>b;

	m=a*b/cmmdc(a,b);
	int k=1,dimq=0,x,y,i;
	up[1]=1;
	cif[1]=1;
	q[++dimq]=1;
	r[1]=1;
	while(k<=dimq)
	{
		x=q[k++];

			y=(x*10+0)%m;
			if(!r[y])
			{
				cif[y]=0;
				up[y]=x;
				q[++dimq]=y;
				r[y]=y;
			}
			if(y==0)
				break;

            y=(x*10+1)%m;
			if(!r[y])
			{
				cif[y]=1;
				up[y]=x;
				q[++dimq]=y;
				r[y]=y;
			}
			if(y==0)
				break;
	}



f.close();
afara(0);
fout.close();
return 0;
}