Cod sursa(job #199419)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 18 iulie 2008 17:49:13
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
const int NMAX=2000002;
int a,b,x,i,j,nr,q[NMAX],p,u,prec[NMAX];
bool r[NMAX],v[NMAX],c[NMAX];
int cmmdc(int x,int y){
    if (y==0) return x;
      else return cmmdc(y,x%y);
    }
int cmmmc(int x,int y){
    return x*(y/cmmdc(x,y));
    } 
int main(){
    bool gasit=false;
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d %d",&a,&b);
    x=cmmmc(a,b);
    p=u=0;q[p]=1;r[1%x]=true;prec[0]=-1;c[0]=1;
    while (!gasit){
          a=p;
          nr=q[p];
          i=(nr*10)%x;
          if (!r[i]){
            q[++u]=i;
            r[i]=true;
            prec[u]=a;
            c[u]=0;
            if (i==0) j=u,gasit=true;
            }
          i++;
          if (i>=x) i-=x;
          if (!r[i]){
            q[++u]=i;
            r[i]=true;
            prec[u]=a;
            c[u]=1;
            if (i==0) j=u,gasit=true;
            }
          p++;
          }
    nr=0;
    while (j>=0) v[++nr]=c[j],j=prec[j]; 
    for (i=nr;i;i--) printf("%d",v[i]);
    return 0;
    }