Cod sursa(job #1827213)

Utilizator MoldovanMoldovan Moldovan Data 11 decembrie 2016 16:15:39
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

using namespace std;
struct lee
{
    unsigned long long  nr;
    int rest;
};
int q[2000020];
int vct_tata[200020];
int adaug[2000020];
int retin[2000020];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a, b , rest1,prod=1;

    scanf("%d %d",&a,&b);
    prod=a*b;
    while(b)
    {
        rest1=a%b;
        a=b;
        b=rest1;
    }
    prod/=a;

    if(prod==1)
    {
        printf("1");
        return 0;
    }
    int p =1, u =1;
    q[1]=1;
    vct_tata[1]=0;
    adaug[1]=1;
    while(p<=u)
    {
    rest1=q[p];p++;
        for(int i = 0 ; i <= 1;i++)
        {
            q[++u]=(rest1*10+i)%prod;
            vct_tata[u]=p-1;
            adaug[u]=i;
            if(q[u]==0)
            {
                int l=p-1,cnt=0;
                retin[++cnt]=i;
                while(l!=1)
                {
                    retin[++cnt]=l;
                    l=vct_tata[l];
                }
                retin[++cnt]=1;
                for(int j = cnt;j>=1;j--)
                {
                    printf("%d",adaug[retin[j]]);
                }
                return 0;
            }
        }
    }
    return 0;
}