Cod sursa(job #1771096)

Utilizator giotoPopescu Ioan gioto Data 5 octombrie 2016 10:48:16
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#define NMAX 2000004
using namespace std;

int x,y,R[NMAX],Last[NMAX],Sol[NMAX];
bool A[NMAX],F[NMAX];
inline int cmmdc(int x, int y){
    int Rest ;
    while(y > 0){
        Rest = x % y;
        x = y;
        y = Rest;
    }
    return x;
}
int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%d%d", &x, &y);
    int M = (x * y) / cmmdc(x,y) ;
    R[1] = 1; A[1] = 1; Last[1] = 0;
    F[1] = 1;
    int st = 1, dr = 1;
    do{
        if(F[(R[st] * 10) % M] == 0){
            R[++dr] = (R[st] * 10) % M;
            F[R[dr]] = 1;
            A[dr] = 0;
            Last[dr] = st;
            if(R[dr] == 0) break;
        }

        if(F[(R[st] * 10 + 1) % M] == 0){
            R[++dr] = (R[st] * 10 + 1) % M;
            F[R[dr]] = 1;
            A[dr] = 1;
            Last[dr] = st;
            if(R[dr] == 0) break;
        }
        ++st;

    }while(1);
    int i = dr, NR = 0;
    while(i > 0){
        Sol[++NR] = A[i];
        i = Last[i];
    }
    for(int i = NR; i >= 1; --i)
        printf("%d", Sol[i]);
    return 0;
}