Cod sursa(job #2037633)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 12 octombrie 2017 16:38:21
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#define DM 2000001
#include <algorithm>
#include <bitset>
#include <fstream>
#include <queue>
#include <string>
using namespace std;

ifstream fi ("multiplu.in");
ofstream fo ("multiplu.out");
bitset <DM> bs;
char cfr[DM];
int a, b, c, prv[DM];
queue <int> q;
string s;

int main()
{
	fi >> a >> b;
	c = a*b/__gcd(a, b);
	if (c == 1)
	{
		fo << 1;
		return 0;
	}
	q.push(1);
	bs[1] = 1, cfr[1] = '1', prv[1] = 0;
	while (!bs[0])
	{
		a = q.front();
		q.pop();
		if (!bs[(a*10)%c])
		{
			bs[(a*10)%c] = 1;
			cfr[(a*10)%c] = '0';
			prv[(a*10)%c] = a;
			q.push((a*10)%c);
		}
		if (!bs[(a*10+1)%c])
		{
			bs[(a*10+1)%c] = 1;
			cfr[(a*10+1)%c] = '1';
			prv[(a*10+1)%c] = a;
			q.push((a*10+1)%c);
		}
	}
	b = 0;
	fo << 1;
	while (b != 1)
	{
		s+=cfr[b];
		b = prv[b];
	}
	for (int i = s.size() - 1; i >= 0; --i)
		fo << s[i];
	return 0;
}