Cod sursa(job #3225845)

Utilizator crina2120Arnautu Cristina-Crina crina2120 Data 19 aprilie 2024 09:59:05
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;

/**

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

int q[2000002], pr, ul;
char c[2000002];
int pred[2000002];
bitset<2000002> fr;
string sol;

int main()
{
	int a, b, x;
	fin >> a >> b;
	x = a / __gcd(a, b) *b;
	pr = ul = 1;
	q[pr] = 1;
	c[pr] = '1';
	fr[1] = 1;
	while (fr[0] == 0)
	{
		a = q[pr];
		pr++;
		b = a *10 % x;
		if (fr[b] == 0)
		{
			fr[b] = 1;
			q[++ul] = b;
			c[ul] = '0';
			pred[ul] = pr - 1;
		}

		if (b == 0)
			break;
		b = (a *10 + 1) % x;
		if (fr[b] == 0)
		{
			fr[b] = 1;
			q[++ul] = b;
			c[ul] = '1';
			pred[ul] = pr - 1;
		}
	}

	while (ul != 0)
	{
		sol += c[ul];
		ul = pred[ul];
	}

	reverse(sol.begin(), sol.end());
	fout << sol;
	return 0;
}