Pagini recente » Cod sursa (job #2808978) | Cod sursa (job #2783559) | Cod sursa (job #2824383) | Cod sursa (job #2570028) | Cod sursa (job #2264753)
#include <bits/stdc++.h>
#define pb push_back
#define DM 2000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
queue<pair<pair<int,int>,int> >Q;
int lcm,a,b;
bitset<DM>viz;
map<int,int>mp;
map<int,bool>rez;
int main()
{
fin>>a>>b;
lcm = a*b/__gcd(a,b);
Q.push({{1,1},1});
while(!Q.empty()){
int curr = Q.front().first.first;
int where=Q.front().first.second;
int r=Q.front().second;
Q.pop();
if(viz[curr]) continue;
viz[curr] = 1;
rez[curr]=r;
mp[curr]=where;
if(!curr)
break;
int R0 = (curr*10)%lcm;
int R1 = (curr*10+1)%lcm;
if(viz[R0]) continue;
Q.push({{R0,curr},0});
if(viz[R1]) continue;
Q.push({{R1,curr},1});
}
string ans;
for(int i=0;i!=1;)
{
if(rez[i])
ans+="1";
else
ans+="0";
i=mp[i];
}
ans+="1";
reverse(ans.begin(),ans.end());
fout<<ans;
return 0;
}
/*#include <bits/stdc++.h>
#define pb push_back
#define DM 2000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
struct elm{
string s;
int r;
};
queue<elm>Q;
int lcm,a,b;
bitset<DM>viz;
int main()
{
fin>>a>>b;
lcm = a*b/__gcd(a,b);
Q.push({"1",1});
while(!Q.empty()){
elm curr = Q.front();
Q.pop();
if(viz[curr.r]) continue;
viz[curr.r] = 1;
if(!curr.r){
fout<<curr.s;
return 0;
}
int R0 = (curr.r*10)%lcm;
int R1 = (curr.r*10+1)%lcm;
Q.push({curr.s+'0',R0});
Q.push({curr.s+'1',R1});
}
return 0;
}*/