Pagini recente » Cod sursa (job #479124) | Cod sursa (job #808477) | Cod sursa (job #1042818) | Cod sursa (job #500575) | Cod sursa (job #2229219)
#include <fstream>
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];
bool cif[N];
bool viz[N];
int q[N],p,u;
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;
q[1]=p=u=1;
while(p<=u) {
int cur=q[p];
p++;
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[++u]=nou;
if(nou==0) {
break;
}
}
}
}
int nod=0,ans=0;
while(nod!=-1) {
q[++ans]=cif[nod];
nod=t[nod];
}
for(int i=ans;i>=1;i--) {
fout<<q[i];
}
fout<<"\n";
return 0;
}