Cod sursa(job #3221983)

Utilizator Simon2712Simon Slanina Simon2712 Data 8 aprilie 2024 19:06:01
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int N=2e6;
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
struct ura{
    int prior,length,cif;
} vc[N];
queue<int> q;
int v[N];
int main()
{
    int a,b,val,l,val2,x,i;
    fin>>a>>b;
    x=a*b;
    x=x/cmmdc(a,b);
    q.push(1);
    vc[1].length=1;
    vc[1].cif=1;
    while(!vc[0].length)
    {
        val=q.front();
        q.pop();
        val2=(val*10)%x;
        if(!vc[val2].length)
        {
            vc[val2].length=vc[val].length+1;
            vc[val2].prior=val;
            vc[val2].cif=0;
            q.push(val2);
        }
        val2=(val*10+1)%x;
        if(!vc[val2].length)
        {
            vc[val2].length=vc[val].length+1;
            vc[val2].prior=val;
            vc[val2].cif=1;
            q.push(val2);
        }
    }
    val=0;
    l=vc[val].length;
    while(val!=1)
    {
        v[l]=vc[val].cif;
        l--;
        val=vc[val].prior;
    }
    v[1]=1;
    l=vc[0].length;
    for(i=1;i<=l;i++)
        fout<<v[i];
    return 0;
}