Pagini recente » Cod sursa (job #3231381) | Borderou de evaluare (job #3173670) | Cod sursa (job #1349125) | Cod sursa (job #2749125) | Cod sursa (job #2530309)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define ll long long
#define Nmax 2000005
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
int a, b, m;
queue <int> Q;
vector <int> ans;
bool resturi[Nmax];
int from[Nmax], cifra[Nmax];
void get_sol(int x)
{
do
{
ans.push_back(cifra[x]);
x=from[x];
} while (x!=-1);
for (int i = int(ans.size())-1; i >= 0; i--) cout << ans[i];
}
int main()
{
f >> a >> b;
m=a*b/__gcd(a, b);
// cout << m << " ";
if (a == 1 && b == 1)
{
g << "1";
return 0;
}
Q.push(1);
resturi[1]=1;
cifra[1]=1;
from[1]=-1;
while (!Q.empty())
{
int x=Q.front();
Q.pop();
int copie=x;
x=x*10+0; x%=m;
if (x == 0)
{
from[0]=copie;
cifra[x]=0;
get_sol(0);
return 0;
}
if (resturi[x] == 0)
{
resturi[x]=1;
cifra[x]=0;
from[x]=copie;
Q.push(x);
}
x=copie*10+1; x%=m;
if (x == 0)
{
from[0]=copie;
cifra[x]=1;
get_sol(0);
return 0;
}
if (resturi[x] == 0)
{
resturi[x]=1;
cifra[x]=1;
from[x]=copie;
Q.push(x);
}
}
return 0;
}