Cod sursa(job #1398929)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 24 martie 2015 14:22:08
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <algorithm>
#include <bitset>
#include <fstream>
#include <string>
#include <queue>
using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

const int kMax = 2e6 + 5;
int a, b, n, v[kMax], up[kMax], digit[kMax];
queue<int> q;


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

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

int main()
{
	fin >> a >> b;
	int cmmmc = lcm(a, b);

	
	v[1] = 1 % cmmmc;
	digit[1] = 1;
	
	int inc = 1, sf = 1;
	while (inc <= sf)
	{
		if (!v[inc])
		{
			string s;
			for (int i = inc; i; i = up[i])
				s += (digit[i] + '0');
			reverse(s.begin(), s.end());
			fout << s << '\n';
			break;
		}
	
		if (digit[inc])
		{
			++sf;
			v[sf] = v[inc] * 10 % cmmmc;
			digit[sf] = 0;
			up[sf] = inc;
		}
		else
		{
			++sf;
			v[sf] = v[inc] * 10 % cmmmc;
			digit[sf] = 0;
			up[sf] = inc;

			++sf;
			v[sf] = (1 + v[inc]) % cmmmc;
			digit[sf] = 1;
			up[sf] = up[inc];
		}
		++inc;
	}
	return 0;
}