Pagini recente » Cod sursa (job #2971684) | Cod sursa (job #1826315) | Monitorul de evaluare | Cod sursa (job #1871754) | Cod sursa (job #3350021)
#include <iostream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
int viz[2000001];
int drum[2000001];
int pref[2000001];
int cif[2000001];
int main()
{
long long a,b;
in>>a>>b;
long long c=(a*b)/__gcd(a,b);
queue<int> q;
int start=1%c;
q.push(start);
viz[start]=1;
cif[start]=1;
while(!q.empty())
{
int pos=q.front();
q.pop();
if(pos==0)
{
break;
}
int nxt=(pos*10)%c;
if(!viz[nxt])
{
viz[nxt]=1;
q.push(nxt);
pref[nxt]=pos;
cif[nxt]=0;
}
nxt=(pos*10+1)%c;
if(!viz[nxt])
{
viz[nxt]=1;
q.push(nxt);
pref[nxt]=pos;
cif[nxt]=1;
}
}
string ans="";
int nr=0;
while(nr!=start)
{
ans.push_back(cif[nr]+'0');
nr=pref[nr];
}
ans.push_back('1');
reverse(ans.begin(),ans.end());
out<<ans;
return 0;
}