Pagini recente » Rating Justin Andrei (Justinelu1998) | Cod sursa (job #1405702) | Cod sursa (job #2446615) | Cod sursa (job #2876435) | Cod sursa (job #392141)
Cod sursa(job #392141)
#include<stdio.h>
#include<bitset>
using namespace std;
#define N 2000005
int a,b,m;
bitset<N> last,viz;
int t[N];
int c[N];
inline int cmmdc(int a,int b)
{
int r;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
void scrie(int x)
{
if(x==-1)
return;
scrie(t[x]);
fputc(last[x]==1 ? '1' : '0',stdout);
}
inline void bfs()
{
int now;
c[0]=1;
int p=0;
int u=0;
viz[1]=1;
t[0]=-1;
last[0]=1;
while(p<=u)
{
now=c[p];
now=(now*10)%m;
if(viz[now]==0)
{
c[++u]=now;
last[u]=0;
t[u]=p;
viz[now]=1;
if(now==0)
{
scrie(u);
return;
}
}
++now;
if(now==m)
now=0;
if(viz[now]==0)
{
c[++u]=now;
last[u]=1;
t[u]=p;
viz[now]=1;
if(now==0)
{
scrie(u);
return;
}
}
++p;
}
}
int main()
{
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
scanf("%d%d",&a,&b);
m=a*b/cmmdc(a,b);
bfs();
return 0;
}