Cod sursa(job #2140298)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 23 februarie 2018 10:53:01
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
using namespace std;
struct ok
{
    int c,r,p;
};
ok m[2000005];
bool f[2000005],sol[2000005];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,r,n;
    scanf("%d%d",&a,&b);
    n=a*b;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    n/=a;
    int p=1,u=1;
    m[u].r=1;
    m[u].p=0;
    m[u].c=1;
    f[1]=1;
    while(p<=u)
    {
        int r1=(m[p].r*10+0)%n;
        if(!f[r1])
        {
            f[r1]=1;
            m[++u].r=r1;
            m[u].p=p;
            m[u].c=0;
            if(r1==0)break;
        }
        r1++;
        if(r1>=n)r1-=n;
        if(!f[r1])
        {
            f[r1]=1;
            m[++u].r=r1;
            m[u].p=p;
            m[u].c=1;
            if(r1==0)break;
        }
        p++;
    }
    int cnt=0;
    while(m[u].p!=0)
    {
        sol[++cnt]=m[u].c;
        u=m[u].p;
    }
    sol[++cnt]=1;
    int i;
    for(i=cnt;i>=1;i--)
        printf("%d",sol[i]);
    return 0;
}