Cod sursa(job #1908285)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 7 martie 2017 00:15:16
Problema Multiplu Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bool v[3000005],cif[3000005],seen[3000005];
int pre[3000005];
int dv,a,b,st,dr;
int q[3000005];
int cmmmc(int a,int b)
{
    int x=a,y=b;
    int r=a%b;
    while(r)
    {
        a=b;b=r;
        r=a%b;
    }
    return (x*y/b);
}
void BuildSol(int dr)
{
    while(dr)
    {
        v[++dv]=cif[dr];
        dr=pre[dr];
    }
}
void afisare()
{
    for(int i=dv;i>=1;i--) fout<<v[i];
    fout<<'\n';
}

int main()
{
    fin>>a>>b;
    int m=cmmmc(a,b);
    if(a==1 && b==1)
    {
        fout<<1<<'\n';
        return 0;
    }
    st=1;
    dr=2;
    q[st]=1;
    cif[1]=1;
    seen[1]=1;
    while(st<dr)
    {
        int rest1=(q[st]*10);
        while(rest1>=m) rest1-=m;
        int rest2=(q[st]*10+1);
        while(rest2>=m) rest2-=m;
        if(!seen[rest1])
        {
            q[dr]=rest1;
            seen[rest1]=1;
            cif[dr]=0;
            pre[dr]=st;
            if(!rest1)
            {
                BuildSol(dr);
                afisare();
                return 0;
            }
            dr++;
        }
        if(!seen[rest2])
        {
            q[dr]=rest2;
            seen[rest2]=1;
            cif[dr]=1;
            pre[dr]=st;
            if(!rest2)
            {
                BuildSol(dr);
                afisare();
                return 0;
            }

            dr++;
        }
        seen[q[st]]=0;
        st++;
    }
    return 0;
}