Cod sursa(job #1819740)

Utilizator cyg_SerbanBFlorin Gheorghe cyg_SerbanB Data 30 noiembrie 2016 19:38:09
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
using namespace std;
int up[5000000],q[5000000],cif[5000000];
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    ifstream cin("multiplu.in");
    ofstream cout("multiplu.out");
    int p=1,u=0,x,y,i,cmmmc,a,b;
    cin>>a>>b;
    cmmmc=a*b/cmmdc(a,b);
    up[1]=1;
    cif[1]=1;
    q[++u]=1;
    while(p<=u)
    {
        x=q[p++];
        for(i=0;i<2;++i)
        {
            y=(x*10+i)%cmmmc;
            if(!up[y])
            {
                up[y]=x;
                cif[y]=i;
                q[++u]=y;
            }
            if(y==0)
                return;
        }
    }
    x=0;
    while(1)
    {
        cout<<cif[x];
        if(x==1)
            return 0;
        x=up[x];
    }
    return 0;
}