Cod sursa(job #530412)

Utilizator MiuMihaiMiu Mihai MiuMihai Data 7 februarie 2011 18:50:42
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

#define MAX 2000010
#define pb push_back

using namespace std;

int a, b;
int tat[MAX], loc[MAX];
vector <int> queViz;

inline int gcd(int a, int b)
{
	if (!b)
		return a;
	return gcd(b, a % b);
}

int main()
{
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);

	scanf("%d %d\n", &a, &b);

	int cmmmc = (a * b) / gcd(a, b);

	tat[1] = 1;
	loc[1] = 1;
	queViz.pb(1);
	for (int i = 0; !tat[0]; i++)
	{
		if (!tat[queViz[i] * 10 % cmmmc])
		{
			tat[queViz[i] * 10 % cmmmc] = queViz[i];

			queViz.pb(queViz[i] * 10 % cmmmc);
		}
		if (!tat[(queViz[i] * 10 + 1) % cmmmc])
		{
			tat[(queViz[i] * 10 + 1) % cmmmc] = queViz[i];
			loc[(queViz[i] * 10 + 1) % cmmmc] = 1;
			
			queViz.pb((queViz[i] * 10 + 1) % cmmmc);
		}
	}

	string strSol;
	for (int i = 0; i != 1; i = tat[i])
		strSol += '0' + loc[i];
	strSol += '1';
	reverse(strSol.begin(), strSol.end());

	cout << strSol;

	fclose(stdin);
	fclose(stdout);
	return 0;
}