Cod sursa(job #2266400)

Utilizator PredaBossPreda Andrei PredaBoss Data 22 octombrie 2018 17:14:12
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
queue<int>Q;
long long lcm,a,b;
const int DM=2e6+5;
int mp[DM];
char rez[DM];
void afis(int pos)
{
    if(pos!=1)
        afis(mp[pos]);
    fout<<rez[pos];
}
void solve()
{
    while(!Q.empty()){
        int curr=Q.front();
        Q.pop();
        int R0=(curr*10)%lcm;
        int R1=(curr*10+1)%lcm;
        if(mp[R0]) continue;
        rez[R0]='0';
        mp[R0]=curr;
        if(R0==0)
            return;
        Q.push(R0);
        if(mp[R1]) continue;
        rez[R1]='1';
        mp[R1]=curr;
        if(R1==0)
            return;
        Q.push(R1);
    }
}
int main()
{
    fin>>a>>b;
    lcm=a*b/__gcd(a,b);
    Q.push(1);
    rez[1]='1';
    mp[1]=1;
    solve();
    afis(0);
    return 0;
}