Cod sursa(job #1332922)

Utilizator raddudjPogonariu Radu raddudj Data 2 februarie 2015 16:18:15
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct INFO {
    bool c;
    int r,t;
};

INFO q[2000005];
bool r[2000005];
vector <int> sol;

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

inline int lcm(int a,int b) {
    int rez=gcd(a,b);
    return rez*(a/rez)*(b/rez);
}

int main() {
    int a,b,last,m,i,rest;
    INFO temp;
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d %d",&a,&b);
    temp.c=1;
    temp.r=1;
    temp.t=0;
    q[1]=temp;
    m=lcm(a,b);
    i=1;
    last=1;
    while(1) {
        ///Adaug 0
        rest=(q[i].r*10+0)%m;
        if(!r[rest]) {
            r[rest]=1;
            temp.c=0;
            temp.r=rest;
            temp.t=i;
            q[++last]=temp;
        }
        if(r[0])
            break;
        ///Adaug 1
        rest=(q[i].r*10+1)%m;
        if(!r[rest]) {
            r[rest]=1;
            temp.c=1;
            temp.r=rest;
            temp.t=i;
            q[++last]=temp;
        }
        if(r[0])
            break;
            i++;
    }
    for(i=last; i>=1;) {
        sol.push_back(q[i].c);
        i=q[i].t;
    }
    reverse(sol.begin(),sol.end());
    for(i=0; i<sol.size(); i++)
        printf("%d",sol[i]);
    printf("\n");
    return 0;
}