Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok

Cod sursa(job #115220)

Utilizator mastermageSchneider Stefan mastermage Data 16 decembrie 2007 11:43:45
Problema Multiplu Scor 100
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 11-12 Marime 0.8 kb
#include <stdio.h>

#define maxN 2000100

int a,b,n;
int vec[maxN],lst[maxN],st,cur,k;

int gcd(int a,int b){int c;do{if(a<b)c=a,a=b,b=c;a%=b;}while(a);return b;}
void inputFunc(){FILE*fi=fopen("multiplu.in","r");fscanf(fi,"%d %d",&a,&b);n=a*b/gcd(a,b);fclose(fi);}

void outputFunc(){
	FILE*fi=fopen("multiplu.out","w");
	int x=0,ul=vec[x];
	while(x!=-1){
		for(int i=ul;ul>vec[x];ul--)fprintf(fi,"0");
		fprintf(fi,"1");ul--;
		x=lst[x];
	}
	while(ul--)fprintf(fi,"0");
	fclose(fi);
}



int main(){
	inputFunc();
	
	vec[1]=1;lst[1]=-1;
	k=2;
	cur=st=10%n;
	
	for(;!vec[0];cur=(cur*st)%n,k++){
		for(int i=n-1;i>0;i--)if(vec[i] && vec[i]<k){
			int u=i+cur;if(u>=n)u-=n;
			if(!vec[u])vec[u]=k,lst[u]=i;
		}
		if(!vec[cur])vec[cur]=k,lst[cur]=-1;
	}
	
	outputFunc();
	return 0;
}