Cod sursa(job #2387818)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 25 martie 2019 11:39:02
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>

using namespace std;

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

int a,b,i,c[2000005],tata[2000005],cif[2000005],f[2000005],sol[2000005];

int main()
{
    fin >> a >> b;
    int auxa = a; int auxb = b;
    while (b != 0)
    {
        int rest = a%b;
        a = b;
        b = rest;
    }
    int val = auxa*auxb/a;
    int p = 1; int u = 1; c[p] = 1; f[1] = 1; cif[1] = 1;
    while (p <= u)
    {
        if (f[(c[p]*10)%val] == 0)
        {
            c[++u] = (c[p]*10)%val; f[c[u]] = 1;
            tata[u] = p; cif[u] = 0;
        }
        if (c[u] == 0)
            break;
        if (f[(c[p]*10+1)%val] == 0)
        {
            c[++u] = (c[p]*10+1)%val; f[c[u]] = 1;
            tata[u] = p; cif[u] = 1;
        }
        if (c[u] == 0)
            break;
        p++;
    }
    int k = 0;
    while (u != 0)
    {
        sol[++k] = cif[u];
        u = tata[u];
    }
    for (i=k; i>=1; i--)
        fout << sol[i];
    return 0;
}