Cod sursa(job #1069903)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 30 decembrie 2013 17:19:09
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<queue>
#define maxn 2000005
using namespace std;
ifstream fi("multiplu.in");
ofstream fo("multiplu.out");

queue <int> q;

int a,b,x,cmmmc;
int poz[maxn];
bool u[maxn]; 

int cmmdc(int a,int b){
    while(a!=0 && b!=0)
      if(a>b)a%=b; else b%=a;
    return (a+b);
}

void rezolva(){
     int nr,x,m;
     m=cmmmc;
     
     q.push(1);
     u[1]=1;
     poz[1]=-1;
     
     while((!q.empty()) && (!poz[0]))
     {
      x=q.front();
      
      nr=(x*10)%m;
      if(poz[nr]==0){
                     u[nr]=0;
                     poz[nr]=x;
                     q.push(nr);
                    }
                    
      nr=(x*10+1)%m;
      if(poz[nr]==0){
                     u[nr]=1;
                     poz[nr]=x;
                     q.push(nr);
                    }
      q.pop();
     }     
}



void tipar(int k){
     if(poz[k]!=-1) tipar(poz[k]);
     fo<<u[k];
}

int main(){
    fi>>a>>b;
    cmmmc=(a*b)/cmmdc(a,b);

    rezolva();
    tipar(0);
    
    fi.close();
    fo.close();
    return 0;
}