Cod sursa(job #115984)

Utilizator goguGogu Marian gogu Data 17 decembrie 2007 15:41:52
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <bitset>
#define MaxN 2100000

using namespace std;

unsigned n, nr, a, b, t[MaxN], cd[MaxN];
bitset<MaxN> ok, cif;

inline void test(unsigned r, unsigned T, unsigned c){
     if (!ok[r]){
        t[r] = T;
        cif[r] = c;
        ok[r] = 1;
        cd[nr++] = r;
     }
}

inline void expand(unsigned x){
     unsigned r=10*x;
     #define W(p) if (r>=(n<<p)) r-=(n<<p);
     W(3) W(2) W(1) W(0)
     test(r, x, 0);
     r++;
     if (r>=n) r-=n;
     test(r, x, 1);
}

inline void refa(unsigned c){
     if (c!=1) refa(t[c]);
     printf("%d", (int)cif[c]);
}

int cmmdc(int a, int b){
    if (!b) return a; else return cmmdc(b, a%b);
}

int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%d %d", &a, &b);
    n = (a*b)/cmmdc(a, b);
    cd[nr++] = 1;
    ok[1]=0;
    cif[1]=1;
    unsigned j=0;
    while (!ok[0]) expand(cd[j++]);
    refa(0);
}