Cod sursa(job #3356036)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 mai 2026 02:42:19
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

int q[2000005];
int pr[2000005];
bitset<2000005> val;

long long get_gcd(long long a, long long b) {
    while(b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    long long a, b;
    fin >> a >> b;
    
    long long k = (a * b) / get_gcd(a, b);
    
    memset(pr, -1, sizeof(pr));
    
    int head = 0, tail = 0;
    
    q[tail++] = 1 % k;
    pr[1 % k] = -2;
    val[1 % k] = 1;
    
    while(head < tail) {
        int curr = q[head++];
        
        if(curr == 0) {
            break;
        }
        
        int next0 = (curr * 10) % k;
        if(pr[next0] == -1) {
            pr[next0] = curr;
            val[next0] = 0;
            q[tail++] = next0;
            if(next0 == 0) break;
        }
        
        int next1 = (curr * 10 + 1) % k;
        if(pr[next1] == -1) {
            pr[next1] = curr;
            val[next1] = 1;
            q[tail++] = next1;
            if(next1 == 0) break;
        }
    }
    
    vector<int> ans;
    int curr = 0;
    while(curr != -2) {
        ans.push_back(val[curr]);
        curr = pr[curr];
    }
    
    reverse(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); ++i) {
        fout << ans[i];
    }
    fout << "\n";
    
    fin.close();
    fout.close();
    return 0;
}