Cod sursa(job #1781712)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 17 octombrie 2016 11:44:18
Problema Multiplu Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#define MAXN 2000000
int c[MAXN],pred[MAXN],st,dr;
char ult[MAXN];
FILE *fin,*fout;
int cmmmc(int a,int b)
{
    int p,r;
    p=a*b;
    while(b)
    {
        r=a%b;
        a=b;b=r;
    }
    return p/a;
}
void drum(int x)
{
    if(x!=1)
        drum(pred[x]);
    fprintf(fout,"%d",ult[x]);
}
void Lee(int MOD)
{
    int x1,x2;
    do
    {
        x1=(c[st]*10)%MOD;
        if(!pred[x1])
        {
            c[dr++]=x1;
            pred[x1]=c[st];
        }
        x2=(c[st]*10+1)%MOD;
        if(!pred[x2])
        {
            c[dr++]=x2;
            pred[x2]=c[st];ult[x2]=1;
        }
        st++;
    } while(st<dr && x1 && x2);
    if(!x1)
        drum(x1);
    else
        drum(x2);
}
int main()
{
    fin=fopen("multiplu.in","r");
    fout=fopen("multiplu.out","w");
    int a,b;
    fscanf(fin,"%d%d",&a,&b);
    c[0]=1;ult[1]=dr=1;
    Lee(cmmmc(a,b));
    fclose(fin);
    fclose(fout);
    return 0;
}