Pagini recente » Cod sursa (job #2651896) | Cod sursa (job #1198887) | Cod sursa (job #2403903) | Cod sursa (job #512592) | Cod sursa (job #2651903)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int N=2e6+1;
int pred[N],ultim[N],v[N];
bool used[N];
queue<int>q;
int a,b,curent,val1,val2,ans;
int cmmdc(int a,int b)
{
if(a*b==0)return a+b;
if(a>b)
{
return cmmdc(b,a%b);
}
else return cmmdc(a,b%a);
}
int main()
{
fin>>a>>b;
int d=a*b/cmmdc(a,b);
q.push(1);
used[1]=1;
while(!q.empty())
{
curent=q.front();
q.pop();
val1=(curent*10)%d;
if(used[val1%d]==0)
{
used[val1]=1;
pred[val1]=curent;
ultim[val1]=0;
if(val1==0)
{
ans=val1;
break;
}
else q.push(val1);
}
val2=(curent*10+1)%d;
if(used[val2%d]==0)
{
used[val2]=1;
pred[val2]=curent;
ultim[val2]=1;
if(val2==0)
{
ans=val2;
break;
}
else q.push(val2);
}
}
int k=0;
while(pred[ans]!=0)
{
v[++k]=ultim[ans];
ans=pred[ans];
}
v[++k]=1;
for(int i=k;i>=1;i--)
{
fout<<v[i];
}
return 0;
}