Cod sursa(job #927358)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 25 martie 2013 19:09:26
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
using namespace std;
struct tip
{
    int cifra;
    int rest;
    int tata;
};
int cmmdc(int a,int b)
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
tip q[2000009];
char ras[2000009];
bool  resturi[2000009];
int main()
{
    int a,b;
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d%d",&a,&b);
    if(a==1&&b==1)
        printf("1\n");
    else
        {
            int cmmmc=a*b/cmmdc(a,b),c,i,j;
            tip aux;
            int primul,ultimul;
            primul=ultimul=1;
            aux.tata=0;
            aux.cifra=1;
            aux.rest=1;
            resturi[1]=true;
            q[1]=aux;
            ultimul++;
            while(primul<=ultimul)
            {
                if(q[primul].rest==0)
                    break;
                for(c=0;c<=1;c++)
                {
                    aux.rest=(q[primul].rest*10+c)%cmmmc;
                    aux.cifra=c;
                    aux.tata=primul;
                    if(resturi[aux.rest]==false)
                    {
                        q[ultimul]=aux;
                        ultimul++;
                        resturi[aux.rest]=true;
                    }
                }
                primul++;
            }
            i=0;
            while(primul!=0)
            {
                i++;
                ras[i]=q[primul].cifra;
                primul=q[primul].tata;
            }
            for(j=i;j>=1;j--)
            {
                printf("%ld",ras[j]);
            }
            printf("\n");
        }
}