Pagini recente » Cod sursa (job #253566) | Cod sursa (job #11643) | Cod sursa (job #251306) | Cod sursa (job #1639920) | Cod sursa (job #254003)
Cod sursa(job #254003)
#include <cstdio>
#include <queue>
#include <string>
using namespace std;
#define MAX_N 2000005
int A, B, M;
int Ant[MAX_N];
string S;
int gcd(int A, int B)
{
if(!B) return A;
return gcd(B, A%B);
}
void search()
{
queue <int> Q;
Q.push(1);
int rest;
while(!Q.empty())
{
int act = Q.front();
Q.pop();
rest = (act * 10) % M;
if(Ant[rest] == 0)
{
Q.push(rest);
Ant[rest] = act;
}
if(rest == 0) return;
rest = (act * 10 + 1) % M;
if(Ant[rest] == 0)
{
Q.push(rest);
Ant[rest] = act;
}
if(rest == 0) return;
}
}
int main()
{
freopen("multiplu.in","rt",stdin);
freopen("multiplu.out","wt",stdout);
scanf("%d %d",&A, &B);
M = B / gcd(A, B) * A;
search();
int act = 0;
while(act != 1)
{
if((Ant[act] * 10) % M == act) S += '0';
else S += '1';
act = Ant[act];
}
S += '1';
reverse(S.begin(), S.end());
printf("%s\n",S.c_str());
}