Cod sursa(job #2653477)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 28 septembrie 2020 10:59:33
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

int  q[2000005], v[2000005], din[2000005], a, b, M;
bool r[2000005];

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

int main() {
    fin >> a >> b; M = a * b / __gcd(a, b);
    q[0] = 1; r[q[0]] = true;
    int i = 0, j = 1, aux;
    while(1) {
        aux = (q[i] * 10) % M;
        if(!r[aux]) {
            din[j] = i;
            q[j++] = aux;
            r[aux] = true;
            if(!aux) break;
        }
        aux = (aux + 1) % M;
        if(!r[aux]) {
            din[j] = i;
            q[j++] = aux;
            r[aux] = true;
            if(!aux) break;
        }
        ++i;
    } i = 0; --j; do {
        v[i++] = q[j];
        j = din[j];
    } while(j != 0);
    
    fout << 1; v[i] = 1;
    for(j = i-1; j >= 0; --j)
        if(v[j] == (v[j+1] * 10) % M)
            fout << 0;
        else fout << 1;
    return 0;
}