Cod sursa(job #1344510)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 16 februarie 2015 19:33:45
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
using namespace std;
int a, b, m, r, p, u;
int c[2000001], t[2000001];
char cif[2000001], f[2000001];
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int main(){
    fin>> a >> b;
    m = a * b;
    while(b != 0){
        r = a % b;
        a = b;
        b = r;
    }
    m /= a;
    p = 1;
    u = 1;
    c[1] = 1;
    cif[1] = 1;
    f[1] = 1;
    if(m == 1){
        fout<< 1;
        return 0;
    }
    while(p <= u){
        if(f[(c[p] * 10) % m] == 0){
            u++;
            c[u] = (c[p] * 10) % m;
            f[(c[p] * 10) % m] = 1;
            cif[u] = 0;
            t[u] = p;
            if(c[u] == 0){
                break;
            }
        }
        if(f[(c[p] * 10 + 1)% m] == 0){
            u++;
            c[u] = (c[p] * 10 + 1)% m;
            cif[u] = 1;
            t[u] = p;
            f[(c[p] * 10 + 1)% m] = 1;
            if(c[u] == 0){
                break;
            }
        }
        p++;
    }
    r = 0;
    while(u != 0){
        r++;
        f[r] = cif[u];
        u = t[u];
    }

    for(a = r; a >= 1; a--){
        fout<< (int) f[a];
    }
    return 0;
}