Cod sursa(job #1521502)

Utilizator o_micBianca Costin o_mic Data 10 noiembrie 2015 16:19:27
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <queue>
#include <vector>
#define DN 2000005

using namespace std;

int pos[DN], digit[DN], parent[DN];

int gcd(int a, int b) {
	for(int r; b; r = a % b, a = b, b = r);
	return a;
}

int main() {
	int a, b;
	//freopen("input.txt", "r", stdin);
	ifstream fin("multiplu.in");
	ofstream fout("multiplu.out");
	fin >> a >> b;
	int lcm = a * b / gcd(a, b);
	pos[1] = 0;
	queue <int> q;
	q.push(1);
	digit[1] = 1;
	parent[1] = 0;
	while(!q.empty()) {
		int elem = q.front();
		q.pop();
		int x = (elem * 10) % lcm;
		if(!pos[x]){
			pos[x] = 1;
			digit[x] = 0;
			parent[x] = elem;
			if(x == 0)
				break;
			q.push(x);
		}
		int y = (x + 1) % lcm;
		if(!pos[y]) {
			pos[y] = 1;
			digit[y] = 1;
			parent[y] = elem;
			if(y == 0)
				break;
			q.push(y);
		}
	}
	vector <short> res;
	int crt = 0;
	while(parent[crt] != 0) {
		res.push_back(digit[crt]);
		crt = parent[crt];
	}
	res.push_back(1);

	for(vector <short>::reverse_iterator it = res.rbegin(); it != res.rend(); ++it)
		fout << *it;
	return 0;
}