Cod sursa(job #3236648)

Utilizator tedicTheodor Ciobanu tedic Data 29 iunie 2024 21:56:50
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int n,m,k;
int pre[2000002];
queue<int>q;
stack<int>st;
bool v[2000002];
int main()
{
    cin>>n>>m;
    k=n*m;
    int e=__gcd(n,m);
    k/=e;
    if(k==1){
        cout<<1;
        return 0;
    }
    q.push(1);
    v[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        int z=x*10,y=x*10+1;
        z%=k,y%=k;
        if(v[z]==0)
            q.push(z),pre[z]=x,v[z]=1;
        if(z==0)
        break;
        if(v[y]==0)
            q.push(y),pre[y]=x,v[y]=1;
        if(y==0)
        break;
    }
    while(!q.empty())
        q.pop();
    //cout<<pre[1].first;
    st.push(0);
    while(pre[st.top()]!=0)
        st.push(pre[st.top()]);
    int rest=1;
    cout<<1;
    st.pop();
    while(!st.empty())
    {
        rest*=10;
        rest%=k;
        if(st.top()==rest)
            cout<<0;
        else if(st.top()-rest==1)
            cout<<1,rest++;
        else
            cout<<1,rest++;
            st.pop();
    }
    //    cout<<v2[st.top()],st.pop();
        return 0;
}