Cod sursa(job #115518)

Utilizator maria_pparcalabescu maria daniela maria_p Data 16 decembrie 2007 12:54:24
Problema Multiplu Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 0.92 kb
#include<cstdio>
long i,j,k,n,max,x,y,p,q,rest[2000000],a,b,r,nr;
int ok(long x){
	while(x!=0){
		if(x%10>1)return 0;
		x/=10;
	}
	return 1;
}
int main(){
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%ld%ld",&x,&y);
	r=x%y;a=x;b=y;
	while(r!=0){
		x=y;
		y=r;
		r=x%y;
	}
	nr=a*b/y;
	p=1;q=1;r=p%nr;n=0;
	while(r!=0 && rest[r]==0){
		rest[r]=q;
		if(r>n)n=r;
		p=p*10+1;
		q++;
		r=p%nr;
	}
	max=-1;x=-1;y=-1;
	for(i=0;i<n;i++)
		for(j=i+1;j<=n;j++)
			if(rest[i]!=0 && rest[j]!=0){
			if(rest[i]>rest[j])k=i-j;
			else k=j-i;
			if(k<0)k+=nr;
			p=nr-k;
			if(ok(p) && k>max){
				max=k;
				x=rest[i];
				y=rest[j];
			}
		}
	if(y>x){
		p=x;
		x=y;
		y=p;
	}
	for(i=0;i<x-y;i++)
		printf("1");
	k=nr-max;q=0;
	while(k!=0){
		q++;
		k/=10;
	}
	for(i=0;i<y-q;i++)
		printf("0");
	printf("%ld\n",nr-max);
	fclose(stdin);
	fclose(stdout);
	return 0;
}