Cod sursa(job #2269920)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 26 octombrie 2018 19:22:58
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

int n, m;
queue < int > Q;
int f[2000100], M[2000100], val[2000100];

void print(int x){
    if (x == 0) return ;
    print (M[x]);
    
    cout << val[x];
    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    ifstream cin("multiplu.in");
    ofstream cout("multiplu.out");
    cin >> n >> m;
    
    int nr = (n * m) / __gcd(n, m);
    
    if (nr == 1) return cout << 1, 0;
    
    int cnt = 0;
    Q.push(1);
    f[1] = ++cnt;
	val[1] = 1;
    
    while (Q.size()){
        int node = Q.front(); Q.pop();
        
        if (node == 0) {
        	print(f[node]);
            return 0;
        }
        
        for (int i = 0; i < 2; i++){
            int next = node * 10 + i;
            int modd = next % nr;
            
            if (f[modd]) continue;

            Q.push(modd);
            f[modd] = ++cnt;
            M[f[modd]] = f[node];
            val[f[modd]] = i;
        }
    }
    
    return 0;
}