Cod sursa(job #349258)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 18 septembrie 2009 19:42:37
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
//ar trebui sa ia 100 puncte

#include<iostream>
#include<string>

using namespace std;

#define nm 2000005

int ab[nm],coada[nm],tata[nm];
char viz[nm],ce[nm];

int main()
{
    int a,b,c,i,aux;
    
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    
    scanf("%d %d",&a,&b);
    
    int p=a*b;
    
    if(b>a)
    {
      aux=a;
      a=b;
      b=aux;
    }
    
    while(b)
    {
      aux=a;
      a=b;
      b=aux%b;
    }
    
    c=p/a;
    
    //rest(coada),viz,tata,ce
    
    int st=1,dr=1;
    
    coada[st]=1%c;
    viz[1]=1;
    
    if(1%c)
    while(st<=dr)
    {
      int rest=coada[st];
      
      //ii bag 0
      int nr=(rest*10)%c;
      
      if(!viz[nr])
      {
        ++dr;
        coada[dr]=nr;
        tata[dr]=st;
        viz[nr]=1;
        ce[nr]=0;
        if(nr==0) break;
      }
      
      nr=(rest*10+1)%c;
      
      if(!viz[nr])
      {
        ++dr;
        coada[dr]=nr;
        tata[dr]=st;
        viz[nr]=1;
        ce[nr]=1;
        if(nr==0) break;
      }
      st++;
    }
    
    int poz=dr;
    
    
    while(poz!=1)
    {
      ab[0]++;
      ab[ab[0]]=ce[coada[poz]];
      poz=tata[poz];
    }
    
    ab[++ab[0]]=1;
    
    for(i=ab[0];i>=1;i--)
      printf("%d",ab[i]);
    
    return 0;
}