Pagini recente » Cod sursa (job #469261) | Cod sursa (job #121136) | Cod sursa (job #2227674) | Cod sursa (job #2940434) | Cod sursa (job #1725162)
#include <iostream>
#include<fstream>
#include<bitset>
#include<queue>
using namespace std;
char str[2000005];
int prec[200005],a,b,n,p,rest,x,i,k;
bitset<2000005> cf,dist;
queue<int> q;
int main()
{
ifstream f("multiplu.in");
ofstream g("multiplu.out");
f>>a>>b;p=a*b;
while(a!=b)
{
if(a>b) a-=b;
else b-=a;
}
n=p/a;
dist[1]=1;
q.push(1);
cf[1]=1;
prec[1]=-1;
while(dist[0]==0)
{
rest=q.front();
q.pop();
for(i=0;i<=1;i++)
{
x=(rest*10+i)%n;
if(dist[x]==0)
{
dist[x]=1;
cf[x]=i;
prec[x]=rest;
q.push(x);
}
}
}
x=0;
while(x!=-1)
{
k++;
str[k]=cf[x]+'0';
x=prec[x];
}
for(k;k>0;k--)
g<<str[k];
return 0;
}