Cod sursa(job #1332912)

Utilizator vazanIonescu Victor Razvan vazan Data 2 februarie 2015 16:08:17
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<cstdio>
using namespace std;
int cmmdc(int a, int b)
{
    int c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
struct INFO
{
    bool c;
    int r, t;
};
INFO q[1000005];
bool r[2000001];
int main()
{
    FILE *in=fopen("multiplu.in", "r"),
         *out=fopen("multiplu.out", "w");
    int n, m, c, p, u, i;
    fscanf(in, "%d%d", &n, &m);
    c=n*m/cmmdc(n, m);
    q[1].c=1;
    q[1].r=1%c;
    q[1].t=0;
    r[q[1].r]=1;
    p=1;
    u=1;
    while(q[u].r)
    {

        if(!r[(q[p].r*10)%c])
        {
            ++u;
            r[(q[p].r*10)%c]=1;
            q[u].c=0;
            q[u].r=(q[p].r*10)%c;
            q[u].t=p;
        }
        if(!r[(q[p].r*10+1)%c])
        {
            ++u;
            r[(q[p].r*10+1)%c]=1;
            q[u].c=1;
            q[u].r=(q[p].r*10+1)%c;
            q[u].t=p;
        }
        ++p;
    }
    int rec=u, rasp[20000], ncf=0;
    while(rec)
    {
        rasp[ncf]=q[rec].c;
        rec=q[rec].t;
        ncf++;
    }
    for(i=ncf-1; i>=0; --i)
    {
        fprintf(out, "%d", rasp[i]);
    }
    return 0;
}