Pagini recente » Cod sursa (job #1554213) | Cod sursa (job #1807225) | Cod sursa (job #2121070) | Cod sursa (job #1553762) | Cod sursa (job #2229218)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int n;
int a,b;
int gcd(int a,int b) {
if(b==0) {
return a;
}
return gcd(b,a%b);
}
const int N=2000000+5;
int t[N];
int cif[N];
bool viz[N];
int main() {
fin>>a>>b;
n=a*b/gcd(a,b);
if(n==1) {
fout<<"1\n";
return 0;
}
viz[1]=1;
t[1]=-1;
cif[1]=1;
queue<int>q;
q.push(1);
while(!q.empty()) {
int cur=q.front();
q.pop();
for(int i=0;i<=1;i++) {
int nou=(cur*10+i)%n;
if(viz[nou]==0) {
viz[nou]=1;
t[nou]=cur;
cif[nou]=i;
q.push(nou);
if(nou==0) {
break;
}
}
}
}
vector<int>ans;
int nod=0;
while(nod!=-1) {
ans.push_back(cif[nod]);
nod=t[nod];
}
reverse(ans.begin(),ans.end());
for(auto itr:ans) {
fout<<itr;
}
fout<<"\n";
return 0;
}