Cod sursa(job #2491307)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 12 noiembrie 2019 11:51:20
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
#define NMAX 2000001

using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bitset<NMAX> fr;
int p[NMAX],v[NMAX],cif[NMAX];
int cmmmc(int a,int b){
    long long p=a,r;
    p*=b;
    while(b){
        r=a%b;
        a=b;
        b=r;
    }
    return p/a;
}
void print(int lastpos){
    while(lastpos>=0){
        fout<<cif[lastpos];
        lastpos=p[lastpos];
    }
}
int main()
{
    int a,b,startpos=0,lastpos=1;
    fin>>a>>b;
    a=cmmmc(a,b);
    p[0]=-1;
    v[0]=1;
    cif[0]=1;
    while(fr[0]==0){

        if(fr[(v[startpos]*10)%a]==0){

            v[lastpos]=(v[startpos]*10)%a;
            fr[(v[startpos]*10)%a]=1;
            cif[lastpos]=0;
            p[lastpos]=startpos;
            if((v[startpos]*10)%a!=0){
            lastpos++;
            }
            else {print(lastpos) ; return 0;}
        }
        if(fr[(v[startpos]*10+1)%a]==0){
            v[lastpos]=(v[startpos]*10+1)%a;
            cif[lastpos]=1;
            fr[(v[startpos]*10+1)%a]=1;
            p[lastpos]=startpos;
            if((v[startpos]*10+1)%a!=0){
            lastpos++;
            }
            else {print(lastpos) ; return 0;}
        }
        startpos++;
    }
    return 0;
}