Cod sursa(job #1414862)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 3 aprilie 2015 10:18:42
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct MULTIPLU
{
    bool c;
    int r,t;
};
MULTIPLU q[2000001];
bool f[2000001];
bool sol[2000001];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,p,u,ca,cb,r0,r1,r,num,i;
    scanf("%d%d",&a,&b);
    ca=a;
    cb=b;
    while(b)
    {
      r=a%b;
      a=b;
      b=r;
    }
    m=ca*cb/a;
    p=u=1;
    q[p].c=1;
    q[p].r=1;
    f[1]=1;
    while(p<=u)
    {
      r0=(q[p].r*10+0)%m;
      if(f[r0]==0)
      {
        ++u;
        q[u].c=0;
        q[u].r=r0;
        q[u].t=p;
        f[r0]=1;
      }
      if(r0==0)
         break;
      r1=(q[p].r*10+1)%m;
      if(f[r1]==0)
      {
        ++u;
        q[u].c=1;
        q[u].r=r1;
        q[u].t=p;
        f[r1]=1;
      }
      if(r1==0)
         break;
      p++;
    }
    num=0;
    while(u>0)
    {
       num++;
       sol[num]=q[u].c;
       u=q[u].t;
    }
    for(i=num; i>=1; i--)
       printf("%d",sol[i]);
    return 0;
}