Cod sursa(job #1758642)

Utilizator hrazvanHarsan Razvan hrazvan Data 17 septembrie 2016 16:22:55
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <cstring>
#define MAXM 2000000
using namespace std;
int prov[MAXM], q[MAXM], st, dr;
char lit[MAXM];

inline int cmmdc(int a, int b){
  int r;
  while(b > 0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

void afis(FILE *out, int x){
  if(x == 1)
    fprintf(out, "1");
  else{
    afis(out, prov[x]);
    fprintf(out, "%d", lit[x]);
  }
}
int main(){
  FILE *in = fopen("multiplu.in", "r");
  int a, b, m, x, nx;
  fscanf(in, "%d%d", &a, &b);
  fclose(in);
  m = a * b / cmmdc(a, b);
  q[0] = 1;
  memset(prov, -1, sizeof prov);
  dr = 1;
  while(prov[0] == -1){
    x = q[st];
    st++;
    nx = x * 10 % m;
    if(prov[nx] == -1){
      prov[nx] = x;
      lit[nx] = 0;
      q[dr++] = nx;
    }
    nx = (x * 10 + 1) % m;
    if(prov[nx] == -1){
      prov[nx] = x;
      lit[nx] = 1;
      q[dr++] = nx;
    }
  }
  FILE *out = fopen("multiplu.out", "w");
  afis(out, 0);
  fclose(out);
  return 0;
}