Cod sursa(job #1398826)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 24 martie 2015 13:36:59
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bitset>
#include <fstream>
#include <string>
#include <queue>
using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

const int kMax = 2e6 + 1;
int a, b;
queue<pair<string, int> > q;

int gcd(int a, int b)
{
	while (b)
	{
		long long r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

int main()
{
	fin >> a >> b;
	long long cmmmc = lcm(a, b);

	q.push(make_pair("1", 1 % cmmmc));
	while (!q.empty())
	{
		string s = q.front().first;
		int mod = q.front().second;
		q.pop();

		if (!mod)
		{
			fout << s << '\n';
			break;
		}

		if (s.back() == '1')
			q.push(make_pair(s + '0', 10 * mod % cmmmc));
		else
		{
			q.push(make_pair(s + '0', 10 * mod % cmmmc));
			
			s.back() = '1';
			q.push(make_pair(s, (1 + mod) % cmmmc));
		}
	}
	return 0;
}