Cod sursa(job #1878141)

Utilizator anisca22Ana Baltaretu anisca22 Data 13 februarie 2017 21:39:36
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
long long a,b,ca,cb,cmmmc,S[2000005],cif[2000005],ok,r,Sum;
queue <int> q;
string rsp;
int main()
{
    fin>>a>>b;
    ca=a;cb=b;
    r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    cmmmc=ca*cb/b;
    q.push(1);
    cif[1]=1;
    S[1]=-1;
    while(ok==0)
    {
        Sum=q.front();
        if(S[(Sum*10+1)%cmmmc]==0)
        {
            q.push((Sum*10+1)%cmmmc);
            S[(Sum*10+1)%cmmmc]=Sum;
            cif[(Sum*10+1)%cmmmc]=1;
            if((Sum*10+1)%cmmmc==0)
                ok=1;

        }
        if(S[(Sum*10)%cmmmc]==0)
        {
            q.push((Sum*10)%cmmmc);
            S[(Sum*10)%cmmmc]=Sum;
            cif[(Sum*10)%cmmmc]=0;
            if((Sum*10)%cmmmc==0)
                ok=1;
        }
        q.pop();
    }
    Sum=0;
    while(Sum!=-1)
    {
        rsp+=(char)(cif[Sum]+'0');
        Sum=S[Sum];
    }
    for(int i=rsp.size()-1;i>=0;i--)
        fout<<rsp[i];
    return 0;
}