Pagini recente » Cod sursa (job #3361127) | Cod sursa (job #3361257) | Cod sursa (job #3361259) | Cod sursa (job #3361258)
#include <fstream>
#include <queue>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
const int MAX_M = 2000000;
int up[MAX_M],
dig[MAX_M];
int M, A, B;
int gcd(int x, int y)
{
int r;
while(y != 0)
{
r = x % y;
x = y;
y = r;
}
return x;
}
inline int lcm(int x, int y)
{
return x / gcd(x, y) * y;
}
void Read()
{
f >> A >> B;
M = lcm(A, B);
}
void Init()
{
for(int i = 0; i < M; i++)
dig[i] = -1;
}
void BFS()
{
queue<int> Q;
up[1] = -1;
dig[1] = 1;
Q.push(1);
while(!Q.empty())
{
int rem = Q.front();
Q.pop();
if(!rem)
return;
for(int d : {0, 1})
{
int val = (rem * 10 + d) % M;
if(dig[val] == -1)
{
up[val] = rem;
dig[val] = d;
Q.push(val);
}
}
}
}
void PrintAns(int rem)
{
if(up[rem] == -1)
g << dig[rem];
else
{
PrintAns(up[rem]);
g << dig[rem];
}
}
int main()
{
Read();
Init();
BFS();
PrintAns(0);
f.close();
g.close();
return 0;
}