Cod sursa(job #124249)

Utilizator azotlichidAdrian Vladu azotlichid Data 18 ianuarie 2008 18:13:03
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SIZE(X) (int)((X).size())
#define TIPA(a, i) (cerr << #a << "[" #i " = " << (i) << "] = " << (a)[i] << endl)
#define TIP(x) (cerr << #x << " = " << (x) << endl)

#define MP make_pair
#define PB push_back
#define INF 0x3F3F3F3F

typedef long long LL;

#define NMAX 1024
#define LMAX 2000005

int A, B, N, qb, qe;
int p[LMAX], q[LMAX];
char u[LMAX];

int gcd(int a, int b)
{
	int c;
	do { c = a%b, a = b, b = c; } while (c != 0);
	return a;
}

int main(void)
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
	scanf("%d %d", &A, &B);
	N = A*B/gcd(A,B);

	memset(p, 0xFF, sizeof(p));

	q[qb=qe=0] = 1;
    u[1] = 1, p[1] = 0;
	for (; qb <= qe; qb++)
	{
		int x = q[qb];
		if (p[(10*x) % N] == -1)
		{
			q[++qe] = (10*x)%N;
			p[q[qe]] = x, u[q[qe]] = 0;
		}
		if (p[(10*x+1) % N] == -1)
		{
			q[++qe] = (10*x+1)%N;
			p[q[qe]] = x, u[q[qe]] = 1;
		}
        if (p[0] != -1) break;
	}

	string Ans;
	int x = 0;
	do {
		Ans += ('0' + u[x]);
		x = p[x];
	} while (x != 0);

	reverse(Ans.begin(), Ans.end());
	printf("%s\n", Ans.c_str());
    return 0;
}