Cod sursa(job #919442)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 17:41:39
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>
#include<deque>
#include<vector>
#include<bitset>
#define nmax 2000010
using namespace std;
int a,b,i,first,m,cmmdc(int,int),poz[nmax],c[nmax];
bitset<nmax>R;
deque<int>Q;
vector<int>sol;
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d%d", &a, &b);
    m=(a*b)/cmmdc(a,b);
    Q.push_back(1);
    for(poz[1]=-1,R[1]=1,c[1]=1;!R[0];)
    {
        first=Q.front();
        if(!R[(first*10)%m])
        {
            R[(first*10)%m]=1;
            poz[(first*10)%m]=first;
            Q.push_back((first*10)%m);
        }
        if(!R[(first*10+1)%m])
        {
            R[(first*10+1)%m]=1;
            c[(first*10+1)%m]=1;
            poz[(first*10+1)%m]=first;
            Q.push_back((first*10+1)%m);
 
        }
        Q.pop_front();
    }
    for(a=0;a!=-1;a=poz[a])
        sol.push_back(c[a]);
    for(i=sol.size();i>0;--i)
        printf("%d", sol[i-1]);
    return 0;
}
int cmmdc(int a, int b)
{
    if(b)return cmmdc(b,a%b);
    return a;
}