Cod sursa(job #1414855)

Utilizator cyg_dobreEduard Dobre cyg_dobre Data 3 aprilie 2015 09:56:47
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<cstdio>
#define MAX 2000000
using namespace std;

int rest[MAX+1];
bool val[MAX+1];
bool viz[MAX+1];
int prec[MAX+1];
int rasp[MAX+1];

int cmmdc(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,n,ic,sf,aux;

    scanf ("%d%d",&a,&b);

    n=a*b/cmmdc(a,b);

    ic=1;
    sf=2;

    rest[1]=1;
    viz[1]=1;
    prec[1]=0;
    val[1]=1;

    while(ic<sf){
        aux=rest[ic]*10%n;
        if (viz[aux]==0){
            rest[sf]=aux;
            viz[aux]=1;
            prec[sf]=ic;
            val[sf]=0;
            sf++;

            if (aux==0){
                sf--;
                ic=sf;
            }
        }
        aux++;
        if (viz[aux]==0 &&ic!=sf){
            rest[sf]=aux;
            viz[aux]=1;
            prec[sf]=ic;
            val[sf]=1;
            sf++;

            if (aux==n){
                sf--;
                ic=sf;
            }
        }

        if (ic!=sf) ic++;
    }

    n=0;
    while(ic!=0){
        n++;
        rasp[n]=val[ic];
        ic=prec[ic];
    }

    for(;n>0;n--)
        printf ("%d",rasp[n]);

    return 0;
}