Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok
Cod sursa(job #115220)
Utilizator | 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;
}