Pagini recente » Cod sursa (job #1245620) | Cod sursa (job #1552415) | Cod sursa (job #1951206) | Cod sursa (job #1998602) | Cod sursa (job #2866374)
#include <fstream>
#include <queue>
using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int a, b;
queue <int> Q;
pair<int, int> ant[2000005];
int getCMMMC(int x, int y)
{
int r = x % y, p = x * y;
while(r)
{
x = y;
y = r;
r = x % y;
}
return p / y;
}
void traceback(int r)
{
if(r == 1)
{
cout<<'1';
return;
}
traceback(ant[r].first);
cout << ant[r].second;
}
int main()
{
cin>>a>>b;
int m = getCMMMC(a, b);
if(1 % m == 0)
{
cout<<1;
return 0;
}
Q.push(1);
while(!Q.empty())
{
int r = Q.front();
Q.pop();
for(int i=0; i<=1; i++)
{
int nr = (1LL * r * 10 + i) % m;
if(ant[nr].first == 0)
ant[nr] = {r, i}, Q.push(nr);
if(nr == 0)
{
traceback(nr);
return 0;
}
}
}
return 0;
}