Cod sursa(job #762050)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 28 iunie 2012 15:11:18
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<fstream>
#define dim 2000003
using namespace std;


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

long long a,b,M,prod;
int T[dim],C[dim],viz[dim],nr[dim];
void cmmmc(){
	int x,y,r;
	prod=a*b;
	r=0;
	x=a;y=b;
	while(y!=0){
		r=x%y;
		x=y;
		y=r;
	}
	prod/=x;
	M=prod;
}
void afis(int x){
	if(x==0){
		return ;
	}
	afis(T[x]);
	g<<nr[x];
}
void find () {
	
	C[1]=nr[1]=1;
	int p,u,now;
	p=u=1;
	int r;
	while( p <= u ) {
		now=C[p];
		for(int i=0;i<=1;i++ ){
			r=(now*10+i)%M;
			if(!viz[r]){
				viz[r]=1;
				C[++u]=(now*10+i)%M;
				nr[u]=i;
				T[u]=p;
			}
		}
		if(r==0){
			afis(u);
			break;
		}
		++p;
	}
}
int main () {
	f>>a>>b;
	
	cmmmc();
	find();
	
	return 0;
	
}