Pagini recente » Cod sursa (job #496526) | Cod sursa (job #389517) | Cod sursa (job #345605) | Cod sursa (job #1429685) | Cod sursa (job #3236638)
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int n,m,k;
pair<int,int>pre[2000005];
queue<pair<int,int>>q;
stack<int>st;
bool v[2000005];
int main()
{
cin>>n>>m;
k=n*m;
int e=__gcd(n,m);
k/=e;
if(k==1){
cout<<1;
return 0;
}
q.push({1,1});
int last=-1;
//cout<<k;
while(!q.empty())
{
int x=q.front().first,t=q.front().second;
q.pop();
int z=x*10,y=x*10+1;
z%=k,y%=k;
if(v[z]==0)
q.push({z,0}),pre[z].first=x,pre[z].second=t,v[z]=1;
if(z==0)
{
last=0;
break;
}
if(v[y]==0)
q.push({y,1}),pre[y].first=x,pre[y].second=t,v[y]=1;
if(y==0)
{
last=1;
break;
}
}
st.push(last);
int poz=0;
while(pre[poz].first!=0)
st.push(pre[poz].second),poz=pre[poz].first;
cout<<1;
st.pop();
while(!st.empty())
cout<<st.top(),st.pop();
return 0;
}