Cod sursa(job #2530310)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 24 ianuarie 2020 17:31:30
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define ll long long
#define Nmax 2000005

using namespace std;

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

int a, b, m;
queue <int> Q;
vector <int> ans;
bool resturi[Nmax];
int from[Nmax], cifra[Nmax];

void get_sol(int x)
{
    do
    {
        ans.push_back(cifra[x]);
        x=from[x];
    }  while (x!=-1);

    for (int i = int(ans.size())-1; i >= 0; i--) g << ans[i];
}

int main()
{
    f >> a >> b;
    m=a*b/__gcd(a, b);
    // cout << m << " ";

    if (a == 1 && b == 1)
    {
        g << "1";
        return 0;
    }

    Q.push(1);
    resturi[1]=1;
    cifra[1]=1;
    from[1]=-1;

    while (!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        int copie=x;
        x=x*10+0; x%=m;
        if (x == 0)
        {
            from[0]=copie;
            cifra[x]=0;
            get_sol(0);
            return 0;
        }
        if (resturi[x] == 0)
        {
            resturi[x]=1;
            cifra[x]=0;
            from[x]=copie;
            Q.push(x);
        }
        x=copie*10+1; x%=m;
        if (x == 0)
        {
            from[0]=copie;
            cifra[x]=1;
            get_sol(0);
            return 0;
        }
        if (resturi[x] == 0)
        {
            resturi[x]=1;
            cifra[x]=1;
            from[x]=copie;
            Q.push(x);
        }
    }

    return 0;
}