Cod sursa(job #1691940)

Utilizator gavrisraulRaul Gavris gavrisraul Data 19 aprilie 2016 20:21:03
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <bitset>
using namespace std;
const int vmax=2000010;
int a, b, nr,nvec,vec[vmax],mod[3000];
bitset <vmax> ap;
char predp[vmax],sol[3000];

inline int cmmdc(int a, int b){
    return (!b) ? a : cmmdc(b, a % b);
}
int main(){
    int i;
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%d %d", &a, &b);
    nr = a * b / cmmdc(a, b);
    int mx = 0;
    ap[0] = 1;
    vec[++nvec] = 0;
    mod[0] = 1;
    int q = 1, w = 0, nnvec, nval;
    while (1) {
        nnvec = nvec;
        for (i = 1; i <= nvec; i++) {
            nval = vec[i] + q;;
            if (nval > nr) nval -= nr;
            if (ap[nval] == 0) {
                vec[++nnvec] = nval;
                ap[nval] = 1;
                predp[nval] = w;
            }
        }
        nvec = nnvec;
        if (ap[nr] == 1) break;
        q = (q * 10) % nr;
        w++;
        mod[w] = q;
    }
    q = nr;
    int pmax = predp[q];
    if (pmax > mx) mx = pmax;
    while (q) {
        sol[predp[q]] = 1;
        q = q - mod[predp[q]];
        if (q < 0) q += nr;
    }
    for (i = pmax; i >= 0; i--) printf("%d", sol[i]);
    return 0;
}