Cod sursa(job #2217433)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 30 iunie 2018 14:32:47
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

//ifstream f("/home/mihai/Documents/c++/A/A.in");
//ofstream g("/home/mihai/Documents/c++/A/A.out");

ifstream f("multiplu.in");
ofstream g("multiplu.out");

const int NMAX = 2e6 + 7;

int pred[NMAX];
int cif[NMAX];
int coada[NMAX];

void solve(int m)
{
	int p = 1;
	int u = 1;
	pred[1] = 1;
	cif[1] = 1;
	coada[1] = 1;
	while(p <= u)
	{
		int x = coada[p++];
		for(int i = 0; i < 2; i++)
		{
			int y = (x * 10 + i) % m;
			if(!pred[y])
			{
				cif[y] = i;
				pred[y] = x;
				coada[++u] = y;
			}
			if(y == 0)
				return;
		}
	}
}

void print(int i)
{
	if(i != 1)
		print(pred[i]);
	g << cif[i];
}

int main()
{
	int a, b;
	f >> a >> b;
	int m = a * b / __gcd(a, b);
	solve(m);
	print(0);
}