Cod sursa(job #612562)

Utilizator 0pt1musOptimus 0pt1mus Data 8 septembrie 2011 18:27:36
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <cstring>

#define vSize 2000001
#define rSize 2000001
#define nSize 2000001
#define dSize 2000001

using namespace std;

ifstream in;
ofstream out;

int v[vSize];
bool r[rSize];
int n[nSize];
int d[dSize];

inline void multiplu(int x)
{
    memset(r,0,sizeof(r));

    r[1]=1;
    v[0]=1;
    v[1]=1;
    n[1]=1;
    d[1]=1;

    for(int ind=1,rest;ind<=v[0];++ind)
    {
        rest=v[ind]*10;
        for(;rest>=x;rest-=x);
        if(rest==0)
        {
            n[ind]=(n[ind]<<1);
            for(;d[ind]>-1;--d[ind])
                out<<((n[ind]&(1<<d[ind]))?1:0);
            out<<'\n';
            return;
        }

        if(!r[rest])
        {
            r[rest]=1;
            v[++v[0]]=rest;
            n[v[0]]=(n[ind]<<1);
            d[v[0]]=d[ind]+1;
        }

        ++rest;
        if(rest==x) rest=0;
        if(rest==0)
        {
            n[ind]=(n[ind]<<1)+1;
            for(;d[ind]>-1;--d[ind])
                out<<((n[ind]&(1<<d[ind]))?1:0);
            out<<'\n';
            return;
        }

        if(!r[rest])
        {
            r[rest]=1;
            v[++v[0]]=rest;
            n[v[0]]=(n[ind]<<1)+1;
            d[v[0]]=d[ind]+1;
        }
    }
}

inline int cmmdc(int A,int B)
{
    int r;

    if(B==0) return A;

    do
    {
        r=A%B;
        A=B;
        B=r;
    }
    while(B);

    return A;
}

int main()
{
    int A,B,x;

    in.open("multiplu.in");
    out.open("multiplu.out");

    in>>A>>B;
    x=(A*B)/cmmdc(A,B);
    if(x<2) out<<x<<'\n';
    else multiplu(x);

    in.close();
    out.close();

    return 0;
}