Cod sursa(job #2269925)

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

using namespace std;

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

void print(int x){
    if (x == 1){
		cout << 1;
		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;
    
    Q.push(1);
	val[1] = 1;
	M[1] = -1;
    
    while (Q.size()){
        int node = Q.front(); Q.pop();
        
        if (node == 0) {
        	print(M[0]);
			cout << val[0];
            return 0;
        }
        
        for (int i = 0; i < 2; i++){
            int next = node * 10 + i;
            int modd = next % nr;
            
            if (M[modd]) continue;

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