Cod sursa(job #805361)

Utilizator misinozzz zzz misino Data 31 octombrie 2012 11:52:13
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<fstream>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
int x,i,a,b,p,r,u,sol,cmmmc,pred[1<<20],cifra[1<<20],c[1<<20];
bool v[1<<20];
char s[1<<20];
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;
        }

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