Cod sursa(job #2518765)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 6 ianuarie 2020 16:19:06
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N=2000001;
bool viz[N];
int pred[N],cif[N],q[N];

int cmmdc (int a, int b)
{
    int r;
    while (a%b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return b;
}
void af (int u)
{
    if (u!=0)
    {
        af(pred[u]);
        out<<cif[u];
    }
}
int main()
{
    int a,b;
    in>>a>>b;
    int m=a*b/cmmdc(a,b);
    int p,u,next;
    p=u=1;
    q[1]=1;
    viz[1]=true;
    cif[1]=1;
    while (p<=u)
    {
        for (int i=0;i<2;i++)
        {
            next=(q[p]*10+i)%m;
            if (!viz[next])
            {
                viz[next]=true;
                cif[++u]=i;
                pred[u]=p;
                q[u]=next;
            }
            if  (next==0)
            {
                af (u);
                return 0;
            }
        }
        p++;
    }
    return 0;
}