Cod sursa(job #1822809)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 5 decembrie 2016 16:49:23
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>
const int NMAX=2000000;
using namespace std;
int cmmmc(int a, int b){
    int cb=b,ca=a;
    while(b!=0) {
        int aux=b;
        b=a%b;
        a=aux;
    }
    int  cmmdc=a;
    int  cmmmc=ca*cb/cmmdc;
    return cmmmc;
}
struct MULTIPLU{
    int c,r,t;
};
MULTIPLU q[NMAX];
bool fr[NMAX+5],sol[NMAX+5];
int main(){
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,rn,p,u;
    MULTIPLU temp;
    scanf("%d%d", &a, &b);
    m=cmmmc(a,b);
    p=u=1;
    temp.c=1;
    temp.r=1;
    temp.t=0;
    fr[1]=1;
    q[u]=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;
    while(u){
		sol[++k]=q[u].c;
		u=q[u].t;
    }
    for(int i=k;i>0;i--)
		printf("%d", sol[i]);
    return 0;
}