Pagini recente » Cod sursa (job #333694) | Cod sursa (job #446231) | Cod sursa (job #88752) | Cod sursa (job #372694) | Cod sursa (job #117183)
Cod sursa(job #117183)
#include <cstdio>
#define INF "multiplu.in"
#define OUF "multiplu.out"
#define NMAX 2000002
#define MIN(a,b) ((a<b)?(a):(b))
using namespace std;
int cmmdc(unsigned long long a,unsigned long long b)
{
unsigned long long r;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
int que[NMAX]={0};
short t[NMAX]={0};
char s[NMAX]={0};
int main()
{
int p,q,a,b,n,k,v;
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
fscanf(in,"%d %d",&a,&b);
if(a>b) p=cmmdc(a,b);
else p=cmmdc(b,a);
n=a*b/p;
// printf("%d\n",n);
p=1;q=1;
que[1]=1;t[1]=1;
while(p<=q)
{
v=que[p];
a=(10*v)%n;
b=(a+1)%n;
if(!t[a]){que[++q]=a;t[a]=t[v]+1;}
if(a==0) break;
if(!t[b]){que[++q]=b;t[b]=t[v]+1;}
if(b==0) break;
++p;
}
// for(k=1;k<=q;++k) printf("%d %hd\n",que[k],t[que[k]]);
// printf("\n");
// printf("%d %d\n",p,q);
k=0;v=0;
while(q>1)
{
do
{
--q;
a=(10*que[q])%n;
b=(a+1)%n;
}while((t[v]-1)!=t[que[q]]||(v!=a&&v!=b));
// printf("%d %hd %d %hd\n",v,t[v],que[q],t[que[q]]);
if(a==v) s[++k]='0';
else s[++k]='1';
v=que[q];
}
fprintf(out,"1");
while(k) fprintf(out,"%c",s[k--]);
fclose(in);fclose(out);
return 0;
}