Cod sursa(job #2271084)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 28 octombrie 2018 00:12:36
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
queue < int > Q;
int M[2000100], val[2000100];
 
void print(int x, ostream& cout){
    if (x == -1) return ;
 
    print (M[x], cout);
    
    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(0, cout);
            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;
}