Pagini recente » Cod sursa (job #2158139) | Cod sursa (job #1457346) | Cod sursa (job #101522) | Cod sursa (job #650029) | Cod sursa (job #1718770)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 1000005
#define MOD 10007
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bool inQ[NMAX];
struct triplet {
char cf;
short lg;
int sum,nr;
};
vector<triplet> multime;
int Prev[4000000];
char res[4000000];
int main() {
int n,i,nr=1,p,ok=0,x,y;
fin>>x>>y;
n=x*y/__gcd(x,y);
if(n<=1) {
fout<<n;
return 0;
}
queue<triplet> Q;
Q.push({'1',1,1,1});
multime.pb({0,0,0,0});
multime.pb({'1',1,1,0});
inQ[1]=1;
triplet a;
while(!Q.empty()) {
a=Q.front();
inQ[a.sum]=0;
Q.pop();
if(a.sum == 0) {
ok=1;
break;
}
//Prev[++nr]=a.nr;
for(i=0;i<=1;++i)
if(!inQ[(a.sum*10+i)%n]) {
inQ[(a.sum*10+i)%n]=1;
Prev[++nr]=a.nr;
multime.pb({i+'0',a.lg+1,(a.sum*10+i)%n,nr});
Q.push({i+'0',a.lg+1,(a.sum*10+i)%n,nr});
}
}
p=a.nr;
while(p) {
res[multime[p].lg]=multime[p].cf;
p=Prev[p];
}
fout<<res+1;
return 0;
}