Cod sursa(job #1878164)

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

        }

        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;
}