Pagini recente » Cod sursa (job #1387016) | Cod sursa (job #1451279) | Cod sursa (job #1754927) | Cod sursa (job #270953) | Cod sursa (job #117060)
Cod sursa(job #117060)
#include <cstdio>
#include <bitset>
#include <vector>
#define dim 2000001
using namespace std;
int A;
int B;
int M;
int P;
int U;
int Cb[dim];
int Cp[dim];
int Cr[dim];
vector <int> V;
bitset <dim> Used;
int Euclid(int x, int y)
{
int r;
while(y)
{
r = x % y;
x = y;
y = r;
}
return x;
}
void Rec(int pos)
{
while(pos)
{
V.push_back(Cb[pos]);
pos = Cp[pos];
}
}
int main()
{
freopen("multiplu.in", "rt", stdin);
freopen("multiplu.out", "wt", stdout);
scanf("%d %d", &A, &B);
M = (A * B) / Euclid(A, B);
P = 1;
U = 1;
Cb[1] = 1;
Cr[1] = 1 % M;
Used[1 % M] = 1;
int r, r1, r2;
while(P <= U)
{
r = Cr[P];
r1 = r * 10;
r2 = r * 10 + 1;
r1 %= M;
r2 %= M;
if(!Used[r1])
{
++ U;
Cb[U] = 0;
Cp[U] = P;
Cr[U] = r1;
Used[r1] = 1;
}
if(!r1)
{
Rec(U);
break;
}
if(!Used[r2])
{
++ U;
Cb[U] = 1;
Cp[U] = P;
Cr[U] = r2;
Used[r2] = 1;
}
if(!r2)
{
Rec(U);
break;
}
++ P;
}
int i, n;
n = V.size();
for(i=n-1; i>=0; --i)
printf("%d", V[i]);
fclose(stdin);
fclose(stdout);
return 0;
}