Cod sursa(job #1540291)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 2 decembrie 2015 16:27:48
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#define AnDrEi 2000000

using namespace std;

struct COSTIN {
  int c,r,t;
} q[AnDrEi];

bool viz[AnDrEi];
bool v[AnDrEi];

int cmmmc( int a, int b ) {
  int r;
  while( b != 0 ) {
    r = a % b;
    a = b;
    b = r;
  }
return a;
}
int main() {
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,p,i,u, rest;
    scanf("%d%d",&a,&b);
    m = a * b / cmmmc(a,b);
    q[1].c = 1;
    q[1].r = 1;
    q[1].t = 0;
    viz[1] = 1;
    p = u = 1;
    while( p <= u ) {
      rest = ( q[p].r * 10 ) % m;
      if( viz[ ( q[p].r * 10 ) % m] == 0 ) {
        u++;
        viz[ ( q[p].r * 10 ) % m ] = 1;
        q[u].t = p;
        q[u].r = rest;
        if(viz[0] == 1)
          break;
      }
      rest = ( q[p].r * 10 + 1 ) % m;
      if( viz[ ( q[p].r * 10 + 1 ) % m] == 0 ) {
          u++;
          q[u].c = 1;
          viz[ ( q[p].r * 10 + 1 ) % m ] = 1;
          q[u].t = p;
          q[u].r = rest;
          if(viz[0] == 1)
          break;
        }
      p++;
    }
    i = 1;
    while( u ) {
    v[i] = q[u].c ;
     i ++;
    u = q[u].t;
    }
    i--;
    while( i > 0 )
    printf("%d",v[i]) , i --;
    return 0;
}