Pagini recente » Cod sursa (job #677911) | Cod sursa (job #1780432) | Cod sursa (job #2156653) | Cod sursa (job #2149435) | Cod sursa (job #3149531)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int a,b,r,m,n,i,j,x,t[N],s[N];
bool f[N],c[N];
queue<int> q;
int main()
{
fin>>a>>b;
m=a*b;
while(b)
{
r=a%b;
a=b;
b=r;
}
m/=a;
if(m==1)
{
fout<<1;
return 0;
}
f[1]=1;
t[1]=0;
c[1]=1;
q.push(1);
while(!q.empty())
{
x=q.front();
q.pop();
n=(x*10+1)%m;
if(!f[n])
{
++j;
f[n]=1;
t[n]=x;
c[n]=1;
q.push(n);
}
if(!n) break;
n=(x*10+0)%m;
if(!f[n])
{
f[n]=1;
t[n]=x;
c[n]=0;
q.push(n);
}
if(!n) break;
}
x=0; j=0;
while(1)
{
s[++x]=c[j];
j=t[j];
if(!j) break;
}
for(i=x;i>=1;--i)
{
fout<<s[i];
}
return 0;
}