Pagini recente » Cod sursa (job #3357272) | Cod sursa (job #2224663) | Cod sursa (job #3357273) | Cod sursa (job #2224665) | Cod sursa (job #3357274)
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int gcd(int a, int b){
if(b==0){
return a;
}else{
return gcd(b, a%b);
}
}
int main(){
int a, b;
fin>>a>>b;
int lcm=a/gcd(a,b)*b;
vector<bool> viz(lcm, false);
vector<int> parent(lcm, -1);
vector<int> digit(lcm, -1);
queue<int> q;
int start=1%lcm;
viz[start]=true;
digit[start]=1;
q.push(start);
while(!q.empty()){
int cur=q.front();
q.pop();
int r0 =(cur*10LL)%lcm;
if(!viz[r0]){
viz[r0]=true;
parent[r0]=cur;
digit[r0]=0;
if(r0==0){
q=queue<int>();
break;
}
q.push(r0);
}
int r1=(cur*10LL+1)%lcm;
if(!viz[r1]){
viz[r1]=true;
parent[r1]=cur;
digit[r1]=1;
if(r1==0){
q=queue<int>();
break;
}
q.push(r1);
}
}
string r="";
int cur=0;
while(cur != -1){
r = to_string(digit[cur])+r;
cur=parent[cur];
}
fout<<r<<'\n';
return 0;
}