Cod sursa(job #2272120)

Utilizator shantih1Alex S Hill shantih1 Data 29 octombrie 2018 18:25:51
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <queue>
#define mx 2000005

using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

int n,nr,i,j,m,a,b;
int r[mx],t[mx];
bool f[mx];
char s[mx];

int cmmdc(int a,int b)
{	int r=a%b;	while(r){a=b;b=r;r=a%b;} return b;	}
int cmmmc(int a,int b)
{	return a*b/cmmdc(a,b);	}

void add(int a,char x)
{
	if(f[a]==0)
	{	f[a]=1;	r[++nr]=a;	t[nr]=i; s[nr]=x;	}
}

int main() {
	
	fin>>a>>b;
	m=cmmmc(a,b);
	
	i=nr=1;
	r[1]=1;
	t[1]=0;
	s[1]='1';
	while(r[i]!=0)
	{
		add(r[i]*10%m,'0');
		add((r[i]*10+1)%m,'1');
		i++;
	}
	string rz;
	while(i!=0)
	{
		rz+=s[i];
		i=t[i];
	}
	for(i=(int)rz.size()-1;i>=0;i--)
		fout<<rz[i];
}