Cod sursa(job #2150492)

Utilizator ElektrykT E S L A P E F E L I E Elektryk Data 3 martie 2018 16:37:02
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
struct ans
{
    int rest;
    int ant;
    char cif;
}q[2000005];
int cmmdc(int a, int b)
{
    if(b==0)
        return a;
    return cmmdc(b,a%b);
}
char viz[2000001];
int a,b,r,m,cmmmc,s,f,ans[105];
int main()
{
    in>>a>>b;
    cmmmc=a*b/cmmdc(a,b);
    s=1;
    q[1].rest=1;
    q[1].ant=0;
    q[1].cif=1;
    viz[1]++;
    f=1;
    while(s<=f)
    {
        int r_cur=(q[s].rest*10+0)%cmmmc;
        if(viz[r_cur]==0)
        {
            viz[r_cur]++;
            f++;
            q[f].rest=r_cur;
            q[f].ant=s;
            q[f].cif=0;
        }
        if(r_cur==0)
            break;
        r_cur=(q[s].rest*10+1)%cmmmc;
        if(viz[r_cur]==0)
        {
            viz[r_cur]++;
            f++;
            q[f].rest=r_cur;
            q[f].ant=s;
            q[f].cif=1;
        }
        if(r_cur==0)
            break;
        s++;
    }
    while(f)
    {
        ans[0]++;
        ans[ans[0]]=q[f].cif;
        f=q[f].ant;
    }
    for(int i=ans[0];i>=1;i--)
        out<<ans[i];
    return 0;
}