Cod sursa(job #1435985)

Utilizator OpportunityVlad Negura Opportunity Data 14 mai 2015 21:05:09
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <string>
#include <queue>

using namespace std;

ifstream fi("multiplu.in");
ofstream fo("multiplu.out");

queue < pair<string, long> > q;


long a,b,xa,xb, r[2000001];

long cmmdc(long a, long b) {
	if (!b) return a; else return (b, a % b);
}

long cmmmc(long a, long b) {
	return (a*b)/ cmmdc(a,b);
}

int main() {
	fi >> a >> b;

	long cmc = cmmmc(a,b);

	q.push(make_pair("1", 1));
	r[1] = 1;

	int t = 1;

	while (!q.empty()) {
		long long auxRest = q.front().second;
		string auxString = q.front().first;
		q.pop();

		// fo << auxRest<< endl;
		// fo << auxString<< endl;

		if (!auxRest) {
			fo << auxString;
			return 0;
		}

		long x1 = (auxRest * 10) % cmc;
		long x2 = (auxRest * 10 + 1) % cmc;
		if (!r[x1]) {
			r[x1] = 1;
			q.push(make_pair(auxString + "0", x1));
		}
		if (!r[x2]) {
			r[x2] = 1;
			q.push(make_pair(auxString + "1", x2));
		}
	}

	return 0;
}