Cod sursa(job #3361139)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 21 iulie 2026 11:34:30
Problema Multiplu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb

#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bool imp(int div,string &nr) {
	int cat = 0;
	int rest = 0;
	for (int i = 0; i < nr.size();++i) {
		cat = cat * 10 + (nr[i] - '0');
		if (cat >= div) {
			cat = cat % div;
		}
	}
	return cat == 0;
}
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}
unordered_map<string, bool>m;
string solve(int a,int b) {
	string start = "1";
	int cmmc = a/ gcd(a, b) *b;
	queue<string>q;
	q.push(start);
	m[start] = 1;
	while (true)
	{
		string crtNr = q.front();
		q.pop();
		if (imp(cmmc, crtNr)) {
			return crtNr;
		}
		else {
			crtNr.push_back('0');
			q.push(crtNr);
			crtNr.pop_back();
			crtNr.push_back('1');
			q.push(crtNr);
		}
	}
}
int main()
{
	int a, b;
	fin >> a >> b;
	fout << solve(a, b);
	return 0;
}