Cod sursa(job #1822810)

Utilizator andrei20003Ionescu Andrei andrei20003 Data 5 decembrie 2016 16:49:33
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
 
using namespace std;

const int NMAX=2000000;
struct MULTIPLU
{
    int c,r,t;
};
 
MULTIPLU q[NMAX+5];
bool fr[NMAX+5],sol[NMAX+5];
int cmmdc(int a,int b) {
    int r;
    while (b>0) {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
	int m,p,u,a,b,rn;
    freopen("multiplu.in", "r",stdin);
    freopen("multiplu.out", "w",stdout);
    scanf("%d%d", &a, &b);
    p=u=1;
    MULTIPLU temp;
    m=(a*b)/cmmdc(a,b);
    temp.c=temp.r=1;
    temp.t=0;
    fr[1]=1;
    q[p]=temp;
    while (p<=u) {
        rn=(q[p].r*10+0)%m;
        if (fr[rn]==0) {
            fr[rn]=1;
            temp.c=0;
            temp.r=rn;
            temp.t=p;
            q[++u]=temp;
            if(rn==0)
                break;
        }
        rn=(q[p].r*10+1)%m;
        if (fr[rn]==0) {
            fr[rn]=1;
            temp.c=1;
            temp.r=rn;
            temp.t=p;
            q[++u]=temp;
            if (rn==0)
                break;
        }
        p++;
    }
    int k=0,i;
    while (u>0) {
        sol[++k]=q[u].c;
        u=q[u].t;
    }
    for (i=k;i>=1;i--)
        printf("%d", sol[i]);
    return 0;
}