Cod sursa(job #392141)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 februarie 2010 20:15:27
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#include<bitset>
using namespace std;
#define N 2000005
int a,b,m;
bitset<N> last,viz;
int t[N];
int c[N];
inline int cmmdc(int a,int b)
{
	int r;
	while(b!=0)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}
void scrie(int x)
{
	if(x==-1)
		return;
	scrie(t[x]);
	fputc(last[x]==1 ? '1' : '0',stdout);
}
inline void bfs()
{
	int now;
	c[0]=1;
	int p=0;
	int u=0;
	viz[1]=1;
	t[0]=-1;
	last[0]=1;
	while(p<=u)
	{
		now=c[p];
		now=(now*10)%m;
		if(viz[now]==0)
		{
			c[++u]=now;
			last[u]=0;
			t[u]=p;
			viz[now]=1;
			if(now==0)
			{
				scrie(u);
				return;
			}
		}
		++now;
		if(now==m)
			now=0;
                if(viz[now]==0)
		{
			c[++u]=now;
			last[u]=1;
			t[u]=p;
			viz[now]=1;
			if(now==0)
			{
				scrie(u);
				return;
			}
		}
		++p;
	}
}
int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);

	scanf("%d%d",&a,&b);
        m=a*b/cmmdc(a,b);
        bfs();

	return 0;
}