Cod sursa(job #2949633)

Utilizator emazareMazare Emanuel emazare Data 1 decembrie 2022 12:02:34
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

queue<int> Q;
bool v[2000005];
int st[2000005];

int cmmdc(int a, int b){
    int r,aux;
    if(a<b){
        aux = a;
        a = b;
        b = aux;
    }
    while(b>0){
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int A,B,N,i,k,nr;
    bool cond;
    fin >> A >> B;
    N = (A*B)/cmmdc(A,B);
    Q.push(1);
    st[1] = 1;
    cond = 1;
    while(cond){
        if(st[(Q.front()*10)%N] == 0){
            Q.push((Q.front()*10)%N);
            st[Q.back()] = Q.front();
            if(Q.back() == 0)
                cond = 0;
        }
        if(cond!=0 && st[(Q.front()*10+1)%N] == 0){
            Q.push((Q.front()*10+1)%N);
            st[Q.back()] = Q.front();
            if(Q.back() == 0)
                cond = 0;
        }
        Q.pop();
    }
    st[1] = 0;
    k = 0;
    nr = Q.back();
    while(st[nr]!=0){
        if(nr == (st[nr]*10)%N)
            v[++k] = 0;
        else
            v[++k] = 1;
        nr = st[nr];
    }
    v[++k] = 1;
    for(i=k;i>0;i--)
        fout << v[i];
    return 0;
}