Cod sursa(job #1332886)

Utilizator Sanduleac_VladSanduleac Vllad Alexandru Sanduleac_Vlad Data 2 februarie 2015 15:49:17
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int A, B;
queue<pair<int, vector<int> > > q;
int viz[2000001];

unsigned int gcd(unsigned int a, unsigned int b) {
    unsigned int r;
    if(a < b)
        a ^= b ^= a ^= b;
    while(b) {
        r = b;
        b = a % b;
        a = r;
    }
    return a;
}

int main() {
    int i, j;
    pair<int, vector<int> > p;
    vector<int> v;
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%d %d", &A, &B);
    A = A * B / gcd(A, B);
    v.push_back(1);
    p.first = 1;
    viz[1] = true;
    p.second = v;
    q.push(p);
    while(true) {
        p = q.front();
        p.first *= 10;
        p.first = p.first % A;
        p.second.push_back(0);
        if(!viz[p.first])
            q.push(p);
        if(p.first == 0)
            break;
        p = q.front();
        p.first *= 10;
        p.first++;
        p.first = p.first % A;
        p.second.push_back(1);
        if(!viz[p.first])
            q.push(p);
        if(p.first == 0)
            break;
        q.pop();
    }
    for(i = 0; i < p.second.size(); i++)
        printf("%d", p.second[i]);
    return 0;
}