Cod sursa(job #3225838)

Utilizator Robert2566_Lungu Robert Robert2566_ Data 19 aprilie 2024 09:51:55
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

/**

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

int q[2000002],pr,ul;
char c[2000002];
int pred[2000002];
bitset<2000002> fr;
string sol;

int main()
{
    int a,b,x;
    fin>>a>>b;
    x=a/__gcd(a,b)*b;
    pr=ul=1;
    q[pr]=1;
    c[pr]='1';
    fr[1]=1;
    while(fr[0]==0)
    {
        a=q[pr];
        pr++;
        b=a*10%x;
        if(fr[b]==0)
        {
            fr[b]=1;
            q[++ul]=b;
            c[ul]='0';
            pred[ul]=pr-1;
        }
        if(b==0)
            break;
        b=(a*10+1)%x;
        if(fr[b]==0)
        {
            fr[b]=1;
            q[++ul]=b;
            c[ul]='1';
            pred[ul]=pr-1;
        }
    }
    while(ul!=0)
    {
    sol+=c[ul];
    ul=pred[ul];
    }
    reverse(sol.begin(),sol.end());
    fout<<sol;
    return 0;
}