Cod sursa(job #1000111)

Utilizator goguGogu Marian gogu Data 22 septembrie 2013 00:15:14
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <bitset>
#define MaxN 2100000
 
using namespace std;
 
unsigned n, nr, a, b, t[MaxN], cd[MaxN];
bitset<MaxN> ok, cif;
 
void test(unsigned r, unsigned T, unsigned c) {
     if (!ok[r]){
        t[r] = T;
        cif[r] = c;
        ok[r] = 1;
        cd[nr++] = r;
     }
}
 
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);
}
 
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;
    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] = 1;
    cif[1] = 1;
    unsigned j = 0;
    while (!ok[0]) {
       expand(cd[j++]);
    }
    refa(0);
}