Cod sursa(job #3238135)

Utilizator Octavian1910Stanislav Octavian George Octavian1910 Data 20 iulie 2024 19:07:23
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <queue>
#include <bitset>
#include <fstream>
#define len 2000001 //2000001
using namespace std;

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

queue<struct x> q;
bitset<len> viz;


struct x
{
    string str;
    int r;
};

int cmmdc(int a,int b)
{
 while(a!=b)
 {
    if(a>b)
    {
        a=a-b;
    }
    else b=b-a;

 }

    return a;
}

int main()
{
    int a,b;
    fin>>a>>b;
    int cmmc=(a*b)/cmmdc(a,b);
    q.push({"1",1});
    while(!q.empty())
    {
        string currentNumber=q.front().str;
        int currentRest=q.front().r;
        q.pop();
        if(currentRest==0)
        {
            fout<<currentNumber;
            return 0;
        }
        if(viz[ (currentRest*10)%cmmc ]==false)
        {
            q.push( {currentNumber+"0", (currentRest*10)%cmmc} );
            viz[(currentRest*10)%cmmc]=1;

        }

         if(viz[ (currentRest*10+1)%cmmc ]==false)
        {
            q.push( {currentNumber+"1", (currentRest*10+1)%cmmc} );
            viz[(currentRest*10+1)%cmmc]=1;
        }
    }

    fout<<"-1";
    return 0;
}