Cod sursa(job #1736649)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 2 august 2016 13:16:26
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include<queue>
#include<bitset>
#define MAXD 2000010
using namespace std;
char s[MAXD];
int previous[MAXD];
bitset<MAXD> digit,seen;
queue<int> Queue;
int Gcd(int a,int b){
    int r;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main(){
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,n,remainder,newRemainder,i,digits=0;
    scanf("%d%d",&a,&b);
    n=(a*b)/Gcd(a,b);
    seen[1]=1;
    Queue.push(1);
    digit[1]=1;
    previous[1]=-1;
    while(seen[0]==0){
        remainder=Queue.front();
        Queue.pop();
        for(i=0;i<=1;i++){
            newRemainder=(remainder*10+i)%n;
            if(seen[newRemainder]==0){
                seen[newRemainder]=1;
                digit[newRemainder]=i;
                previous[newRemainder]=remainder;
                Queue.push(newRemainder);
            }
        }
    }
    i=0;
    while(i!=-1){
        digits++;
        s[digits]=digit[i]+'0';
        i=previous[i];
    }
    for(i=digits;i>=1;i--)
        printf("%c",s[i]);
    return 0;
}