Cod sursa(job #2400272)

Utilizator DanutAldeaDanut Aldea DanutAldea Data 8 aprilie 2019 16:20:43
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <bitset>
using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

int a,b,m,v[2000001],t[2000001],c[2000001],p,u;
bitset <2000001> f;

int cmmdc(int a,int b){
    while(b!=0){
        a=a%b;
        swap(a,b);
    }

    return a;
}

void afis(int u){
    if(t[u]!=0)
        afis(t[u]);
    fout<<c[u];
}

int main(){
    fin>>a>>b;
    m=a/cmmdc(a,b)*b;

    p=1;
    v[++u]=1;
    c[1]=1;
    f[1]=1;

    while(p<=u){

        if( f[(v[p]*10)%m] == 0 ){

            u++;
            t[u]=p;
            v[u]=(v[p]*10)%m;
            c[u]=0;
            f[(v[p]*10)%m]=1;

            if((v[p]*10)%m==0)
                break;
        }

        if( f[(v[p]*10+1)%m] == 0 ){

            u++;
            t[u]=p;
            v[u]=(v[p]*10+1)%m;
            c[u]=1;
            f[(v[p]*10+1)%m]=1;

            if((v[p]*10+1)%m==0)
                break;
        }

        p++;
    }

    afis(u);

    return 0;
}