Cod sursa(job #3142662)

Utilizator maryyMaria Ciutea maryy Data 23 iulie 2023 10:38:08
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
bool vis[2000005];
int f[1000006], l[1000006];
int main()
{
    int a, b, cmmdc, cm;
    in>>a>>b;
    queue <pair<long long, long long>>q;
    cmmdc=__gcd(a, b);
    cm=a*b/cmmdc;
    q.push({1, 1});
    while(!q.empty())
    {
        int x1=q.front().first;
        int add0=(q.front().first)*10;
        int add1=add0+1;
        add0%=cm;
        add1%=cm;
        q.pop();
        vis[x1]=1;
        if(vis[add0]==0)
        {
            q.push({add0, 0});
            vis[add0]=1;
            f[add0]=x1;
            l[add0]=0;
        }
        if(vis[add1]==0)
        {
            q.push({add1, 1});
            vis[add1]=1;
            f[add1]=x1;
            l[add1]=1;
        }
    }
    int pas=0;
    int i=0;
    char s[1000006];
    l[1]=-1;
    //out<<0; return 0;
    while(l[pas]!=-1)
    {
        s[i]='0'+l[pas];
        pas=f[pas];
        i++;
        //if(i<=10) out<<pas<<" ";
    }
    out<<1;
    for(int j=i-1; j>=0; j--)
    {
        out<<s[j];
    }
}