Cod sursa(job #805368)

Utilizator misinozzz zzz misino Data 31 octombrie 2012 12:13:28
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
int x,i,a,b,p,r,u,cmmmc,pred[1<<21],cifra[1<<21],sol[1<<10],c[1<<21];
bool v[1<<21];
int gcd(int a,int b)
{if(b==0)
	return a;
else
	return gcd(b,a%b);
}
int main()
{
    f>>a>>b;
    cmmmc=a*b/gcd(a,b);
    c[1]=1;
    cifra[1]=1;
    v[1]=true;
    p=1;
    u=1;
    while(p<=u&&!v[0])
    {
        x=c[p];
        ++p;
        r=(x*10)%cmmmc;
        if(!v[r])
        {
            v[r]=true;
            cifra[r]=0;
            pred[r]=x;
            ++u;
            c[u]=r;
        }
        r=(x*10+1)%cmmmc;
        if(!v[r])
        {
            v[r]=true;
            cifra[r]=1;
            pred[r]=x;
            ++u;
            c[u]=r;
        }

    }
    sol[1]=cifra[0];
    sol[0]=1;
    r=pred[0];
    while(r)
    {
        ++sol[0];
        sol[sol[0]]=cifra[r];
        r=pred[r];
    }
    for(i=sol[0];i;--i)
    g<<sol[i];
    g<<'\n';
    return 0;
}