Cod sursa(job #1962323)

Utilizator 00MikeComputer00Mihnea Andreescu 00MikeComputer00 Data 11 aprilie 2017 18:17:49
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
const int MAX=2000000;
struct fint
{
	int c,r,t;
};
fint q[MAX+5];
bool f[MAX+5],sol[MAX+5];
int main()
{
	int a,b,m,ca,cb,r,p,u;
	cin>>a>>b;
	ca=a;
	cb=b;
	while(b>0)
	{
		r=a%b;
		a=b;
		b=r;
	}
	m=ca/a*cb;
	p=u=1;
	q[p].c=1;
	q[p].r=1;
	q[p].t=0;
	f[q[p].r]=1;
	while(p<=u)
	{
		r=(q[p].r*10+0)%m;
		if(f[r]==0)
		{
			u++;
			q[u].c=0;
			q[u].r=r;
			q[u].t=p;
			if(r==0)
				break;
		}
		r=(q[p].r*10+1)%m;
		if(f[r]==0)
		{
			u++;
			q[u].c=1;
			q[u].r=r;
			q[u].t=p;
			if(r==0)
				break;
		}
		p++;
	}
	int i,k;
	k=0;
    while(u)
    {
        sol[++k]=q[u].c;
        u=q[u].t;
    }
    for(i=k;i>=1;i--)
    {
        cout<<sol[i];
    }
    cin.close();
    cout.close();
	return 0;
}