Cod sursa(job #1435991)

Utilizator OpportunityVlad Negura Opportunity Data 14 mai 2015 21:07:54
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 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; 
	return cmmdc(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();

		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;
}