Pagini recente » Cod sursa (job #502262) | Cod sursa (job #2594093) | Cod sursa (job #2319750) | Cod sursa (job #251993) | Cod sursa (job #2651929)
#include <fstream>
#include <queue>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
const int N=2000001;
queue<long> q;
pair<int, int> rest[N];
bool nr[15],drum[N];
int main()
{
int a,b,r,ca,cb,m;
in>>a>>b;
ca=a;
cb=b;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
m=ca*cb/a;
q.push(1);
rest[1].first=0;
rest[1].second=1;
drum[1]=1;
a=-1;
int prim;
while(!q.empty())
{
prim = q.front();
q.pop();
a=(prim*10)%m;
if (!drum[a])
{
q.push(a);
rest[a].first = prim;
rest[a].second = 0;
drum[a]=1;
}
if (a == 0)
{
break;
}
a=(prim*10+1)%m;
if(!drum[a])
{
q.push(a);
rest[a].first=prim;
rest[a].second=1;
drum[a]=1;
}
if(a==0)
{
break;
}
}
int cnt=0;
while(rest[a].first!=0)
{
nr[cnt++]=rest[a].second;
a=rest[a].first;
}
nr[cnt]=1;
for(int i=cnt; i>=0; i--)
{
out<<nr[i];
}
return 0;
}