Cod sursa(job #1250420)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 28 octombrie 2014 09:14:59
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
using namespace std;
int a, b, m, r, p, u;
int c[2000001], t[2000001];
char cif[2000001], f[2000001];
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int main(){
	fin>> a >> b;
	m = a * b;
	while(b != 0){
		r = a % b;
		a = b;
		b = r;
	}
	m /= a;
	p = 1;
	u = 1;
	c[1] = 1;
	cif[1] = 1;
	f[1] = 1;
	if(m == 1){
		fout<< 1;
		return 0;
	}
	while(p <= u){
		if(f[(c[p] * 10) % m] == 0){
			u++;
			c[u] = (c[p] * 10) % m;
			f[(c[p] * 10) % m] = 1;
			cif[u] = 0;
			t[u] = p;
			if(c[u] == 0){
				break;
			}
		}
		if(f[(c[p] * 10 + 1)% m] == 0){
			u++;
			c[u] = (c[p] * 10 + 1)% m;
			cif[u] = 1;
			t[u] = p;
			f[(c[p] * 10 + 1)% m] = 1;
			if(c[u] == 0){
				break;
			}
		}
		p++;
	}
	r = 0;
	while(u != 0){
		r++;
		f[r] = cif[u];
		u = t[u];
	}
	
	for(a = r; a >= 1; a--){
		fout<< (int) f[a];
	}
	return 0;
}