Cod sursa(job #1700546)

Utilizator mihai2003LLL LLL mihai2003 Data 10 mai 2016 19:31:36
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
const int nmax=2000000;
bitset  <nmax+5>viz;
struct nyes{
  bool c;
  int t,r;
};
nyes q[nmax+5];
int cmmdc(int a,int b){
    if(b==0)
        return a;
    return cmmdc(b,a%b);
}
int main()
{

    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,ca,cb,p,u,r,k;
    cin>>a>>b;
    ca=a;cb=b;
    m=a*b/cmmdc(a,b);
    p=u=1;
    q[u].c=1;q[u].r=1;q[u].t=0;
    viz[1]=1;
    while (p<=u){
        r=(q[p].r*10+0)%m;
        if(viz[r]==0){
            ++u;
            q[u].c=0;q[u].r=r;
            q[u].t=p;viz[r]=1;
            if(r==0){
                k=0;
                while(u){
                    viz[++k]=q[u].c;
                    u=q[u].t;
                }
                for(int i=k;i>=1;--i)
                    printf("%d",(int)viz[i]);
                break;
            }
        }
        r=(q[p].r*10+1)%m;
        if(viz[r]==0){
            ++u;
            q[u].c=1;q[u].r=r;
            q[u].t=p;viz[r]=1;
            if(r==0){
                k=0;
                while(u){
                    viz[++k]=q[u].c;
                    u=q[u].t;
                }
                for(int i=k;i>=1;--i)
                    printf("%d",(int)viz[i]);
                break;
            }
        }
        ++p;
    }
    return 0;
}