Cod sursa(job #2966662)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 18 ianuarie 2023 08:16:16
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("multiplu.in");
ofstream cout("multiplu.out");

const int NMAX = 2e6;
vector <char> inf(35);

struct p{

    vector <char> x;

};

p min_num[NMAX + 1];

queue <vector <char>> q;
int cmmmc;

int cmmdc(int x, int y){

    int r = 0;
    while(y){

        r = x % y;
        x = y;
        y = r;

    }

    return x;
}

int modulo(vector <char> x, int p){

    int ans = 0;
    for(auto e : x){

        ans = ans * 10 + (e - 48);
        ans %= p;

    }

    return ans;

}

bool mai_mare(vector <char> a, vector <char> b){

    if(a.size() < b.size())
        return 0;

    if(a.size() > b.size())
        return 1;

    for(int i = 0; i < a.size(); i++)
        if(a[i] < b[i])
            return 0;

    return 1;
}

void bfs(vector <char> x){

    q.push(x);
    min_num[1].x.push_back('1');

    while(!q.empty()){

        vector <char> x = q.front();
        q.pop();

        int rm = modulo(x, cmmmc);
        min_num[rm].x = x;

        if(rm == 0)
            return;

        rm *= 10;
        rm %= cmmmc;

        x.push_back('0');
        
        if(mai_mare(min_num[rm].x, x)){
            
            min_num[rm].x = x;
            q.push(x);
        
        }

        x.pop_back();
        x.push_back('1');

        rm = rm * 10 + 1;
        rm %= cmmmc;

        if(mai_mare(min_num[rm].x, x)){
            
            min_num[rm].x = x;
            q.push(x);
        
        }
        

    }

}

int main(){

    int x = 0, y = 0;
    cin >> x >> y;

    if(x == y){

        cout << x;
        return 0;

    }

    cmmmc = x * y / cmmdc(x, y);
    
    for(int i = 0; i <= 30; i++)
        inf[i] = '9';

    for(int i = 0; i < cmmmc; i++)
        min_num[i].x = inf;

    vector <char> temp;
    temp.push_back('1');

    bfs(temp);
    for(auto e : min_num[0].x)
        cout << e;

}