Cod sursa(job #593329)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 2 iunie 2011 11:56:04
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
# include <fstream>
using namespace std;

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

inline int cmmdc (int a, int b)
{
	int r;
	while (b)
	{
		r = a % b;
		a = b;
		b = r;
	}
	
	return a;
}

int q[2000010], st = 1, dr = 1, a, b, i;
int v[2000010];
int nr[2000010];
int t[2000010];

int m;

void afis (int i){
	if (i == 0) return ;
	afis (t[i]);
	g << nr[i];
}

int main ()
{
	f >> a >> b;
	
	q[1] = nr[1] = v[1] = 1;
	
	m = a * b / cmmdc (a, b);
	
	while (st <= dr)
	{
		int num = q[st];
		for (i = 0; i <= 1; ++i)
		{
			int val = (num * 10 + i) % m;
			if (!v[val])
			{
				v[val] = 1;
				++dr;
				q[dr] = val;
				nr[dr] = i;
				t[dr] = st;
			}
			if (val == 0)
			{
				afis (dr);
				
				g.close ();
				return 0;
			}
		}
		++st;
	}
}