Cod sursa(job #2651903)

Utilizator BogdanFarcasBogdan Farcas BogdanFarcas Data 23 septembrie 2020 19:16:46
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int N=2e6+1;

int pred[N],ultim[N],v[N];
bool used[N];
queue<int>q;
int a,b,curent,val1,val2,ans;

int cmmdc(int a,int b)
{
    if(a*b==0)return a+b;
    if(a>b)
    {
        return cmmdc(b,a%b);
    }
    else return cmmdc(a,b%a);
}

int main()
{
    fin>>a>>b;
    int d=a*b/cmmdc(a,b);
    q.push(1);
    used[1]=1;
    while(!q.empty())
    {
        curent=q.front();
        q.pop();
        val1=(curent*10)%d;
        if(used[val1%d]==0)
        {
            used[val1]=1;
            pred[val1]=curent;
            ultim[val1]=0;
            if(val1==0)
            {
                ans=val1;
                break;
            }
            else q.push(val1);
        }
        val2=(curent*10+1)%d;
        if(used[val2%d]==0)
        {
            used[val2]=1;
            pred[val2]=curent;
            ultim[val2]=1;
            if(val2==0)
            {
                ans=val2;
                break;
            }
            else q.push(val2);
        }
    }
    int k=0;
    while(pred[ans]!=0)
    {
        v[++k]=ultim[ans];
        ans=pred[ans];
    }
    v[++k]=1;
    for(int i=k;i>=1;i--)
    {
        fout<<v[i];
    }
    return 0;
}