Cod sursa(job #2658683)

Utilizator tomaionutIDorando tomaionut Data 14 octombrie 2020 19:41:31
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int a,b,ok;
int q[2000005],fr[2000005];
bitset <2000005> bit;
int pred[2000005];
int pr,ul,x,rest;
stack <int> st;
void solve(int y)
{
    rest=(x*10+y)%a;
    if (rest==0)
    {
        ok=1;
        q[++ul]=rest;
        pred[ul]=pr;
        bit[ul]=y;
    }
    else
    {
        if (fr[rest]==0)
        {
            q[++ul]=rest;
            pred[ul]=pr;
            bit[ul]=y;
            fr[rest]=1;
        }
    }
}
int main()
{

    fin >> a >> b;
    a=a*b/__gcd(a,b);
    pr=ul=0;
    q[pr]=1;
    fr[1]=1;
    bit[0]=1;
    ok=0;
    while (ok==0)
    {
        x=q[pr];
        solve(0);
        solve(1);
        pr++;
    }

    while (ul)
    {
        st.push((int)bit[ul]);
        ul=pred[ul];
    }
    fout << 1;
    while (!st.empty())
    {
        fout << st.top();
        st.pop();
    }


    return 0;
}