Pagini recente » Cod sursa (job #142417) | Cod sursa (job #1794550) | Cod sursa (job #175588) | Cod sursa (job #1776327) | Cod sursa (job #1333176)
#include<cstdio>
#include<vector>
#define NMAX 2000010
using namespace std;
int m,last,tata;
int a,b,i;
bool v[NMAX];
vector<int> sol;
int lcm(int a,int b);
void SetInput();
void Calculate();
void Find_Solution();
void Solve();
struct INFO
{
bool c;
int r,t;
};
INFO q[NMAX];
int main()
{
FILE *fin,*fout;
fin=fopen("multiplu.in","r");
fout=fopen("multiplu.out","w");
fscanf(fin,"%d%d",&a,&b);
Solve();
for(i; i>=0; --i)
fprintf(fout,"%d",sol[i]);
return 0;
}
// FUNCTIONS
int lcm(int a,int b)
{
int x=a,y=b,r;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
return (x/a)*y;
}
void SetInput()
{
m=lcm(a,b);
last=0;
q[last].c=1;
q[last].r=1%m;
v[q[last].r]++;
q[last].t=0;
tata=0;
}
void Calculate()
{
while(q[last].r!=0)
{
if(!v[q[tata].r*10])
{
++last;
q[last].c=0;
q[last].r=(q[tata].r*10+0)%m;
q[last].t=tata;
v[q[last].r]++;
}
if(q[last].r==0)
break;
if(!v[q[tata].r*10+1])
{
++last;
q[last].c=1;
q[last].r=(q[tata].r*10+1)%m;
q[last].t=tata;
v[q[last].r]++;
}
++tata;
}
}
void Find_Solution()
{
while(q[last].t!=last)
{
sol.push_back(q[last].c);
last=q[last].t;
}
sol.push_back(1);
i=sol.size()-1;
}
void Solve()
{
SetInput();
Calculate();
Find_Solution();
}