Cod sursa(job #1766228)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 27 septembrie 2016 18:44:35
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

using namespace std;

struct punct
{
    int x,y,z;
};

punct v[2000010];
char vaz[2000010];
char v1[2000010];

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,r,l,k;
    scanf("%d%d",&a,&b);
    m=a*b;
    r=a%b;
    while(r>0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    m=m/b;
    r=1;l=1;
    v[r].x=1;
    v[r].y=0;
    v[r].z=1;
    vaz[1]=1;
    while(1)
    {
        if(vaz[v[r].x*10%m]==0)
        {
            vaz[v[r].x*10%m]=1;
            l++;
            v[l].y=r;
            v[l].x=v[r].x*10%m;
            v[l].z=0;
            if(vaz[0]==1) {k=l;break;}
        }
        if(vaz[(v[r].x*10+1)%m]==0)
        {
            vaz[(v[r].x*10+1)%m]=1;
            l++;
            v[l].y=r;
            v[l].x=(v[r].x*10+1)%m;
            v[l].z=1;
            if(vaz[0]==1) {k=l;break;}
        }
        r++;
    }
    while(1)
    {
        v1[0]++;
        v1[v1[0]]=v[k].z;
        if(v[k].y==0) break;
        else k=v[k].y;
    }
    for(int i=v1[0];i>=1;i--)
        printf("%d",v1[i]);
    return 0;
}