Cod sursa(job #1097282)

Utilizator sandugavrilaGavrila Alexandru sandugavrila Data 3 februarie 2014 11:49:07
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>

using namespace std;
struct queue
{
  bool c;
  int r,pred;
}q[2000005],temp;
bool viz[2000005],s[2000005];
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
      r=a%b;
      a=b;
      b=r;
    }
    return a;
}
void sol(int u)
{
    int i=0;
    while(u)
    {
        s[++i]=q[u].c;
        u=q[u].pred;
    }
    for(u=i;u>=1;u--)
        printf("%d",s[u]);
}
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,i,m,p,u,r;
    scanf("%d%d",&a,&b);
    m=a*b/cmmdc(a,b);
    p=u=1;
    q[p].c=1;
    q[p].r=1;
    q[p].pred=0;
    viz[1]=1;
    while(p<=u)
    {
        for(i=0;i<=1;i++)
        {
            r=(q[p].r*10+i)%m;
            if(viz[r]==0)
            {
                temp.c=i;
                temp.r=r;
                temp.pred=p;
                viz[r]=1;
                q[++u]=temp;

            }
            if(r==0)
            {
                sol(u);
                return 0;
            }
        }
        p++;
    }
    return 0;
}