Cod sursa(job #2801308)

Utilizator tomaionutIDorando tomaionut Data 15 noiembrie 2021 21:16:52
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int a, b,n;
bool viz[2000005];
int father[2000005], c[2000005];
int gcd(int x, int y)
{
    int r;
    while (y)
    {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}
vector <int> v;
queue<int> q;
void Afisare(int x)
{
    while (x)
    {
        v.push_back(c[x]);
        x = father[x];
    }
    for (int i = v.size() - 1; i >= 0; i--)
        fout << v[i];
}
int main()
{
    int x, y;
    fin >> a >> b;
    a = a * b / gcd(a, b);
    q.push(1);
    father[1] = 0;
    viz[1] = 1;
    c[1] = 1;
    while (1)
    {
        n = q.front();
        x = (n * 10) % a;
        y = (n * 10 + 1) % a;
        q.pop();
        if (x == 0)
        {   
            v.push_back(0);
            Afisare(n);
            return 0;
        }
        if (y == 0)
        {
            v.push_back(1);
            Afisare(n);
            return 0;
        }
        if (viz[x] == 0)
        {
            viz[x] = 1;
            father[x] = n;
            c[x] = 0;
            q.push(x);
        }
        if (viz[y] == 0)
        {
            viz[y] = 1;
            father[y] = n;
            c[y] = 0;
            q.push(y);
        }
    }
   


    return 0;
}