Cod sursa(job #1333368)

Utilizator PikachuPikachu Pikachu Data 3 februarie 2015 00:53:08
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

struct INFO{
	int c, r, t;
};

vector <INFO> v;
stack <int> st;
bool rest[2000001];

int cmmdc(int a, int b) {
	int c;
	while(b) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int main() {
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	int a, b, m, n = 1;
	INFO aux;

	scanf("%d%d", &a, &b);

	m = a * b / cmmdc(a, b);

	aux.c = 1;
	aux.r = 1;
	aux.t = -1;
	rest[1] = 1;
	v.push_back(aux);

	for(int i = 0; ; ++ i){
		// 0
		aux.c = 0;
		aux.r = v[i].r * 10 % m;
		aux.t = i;
		if(aux.r == 0) {
			v.push_back(aux);
			++ n;
			break;
		}
		if(!rest[aux.r]) {
			rest[aux.r] = 1;
			v.push_back(aux);
			++ n;
		}
		// 1
		aux.c = 1;
		aux.r = (v[i].r * 10 + 1)% m;
		aux.t = i;
		if(aux.r == 0) {
			v.push_back(aux);
			++ n;
			break;
		}
		if(!rest[aux.r]) {
			rest[aux.r] = 1;
			v.push_back(aux);
			++ n;
		}		
	}

	-- n;

	while(v[n].t != -1) {
		st.push(v[n].c);
		n = v[n].t;
	}

	printf("1");

	while(!st.empty()) {
		printf("%d", st.top());
		st.pop();
	}

	return 0;
}