Cod sursa(job #2825467)

Utilizator lolismekAlex Jerpelea lolismek Data 4 ianuarie 2022 19:22:22
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 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];
    return 0;
}