Cod sursa(job #1905018)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 5 martie 2017 21:18:17
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#define VAL 2000005
#define CIF 35

using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

int A, B, D, M;
int rest[CIF], i;
int v[VAL], K, j;
int prec[VAL], nr;
int app[VAL], c[CIF];
bool ok;

int GCD(int A, int B)
{
    if (B==0)
      return A;
    else
      return GCD(B, A % B);
}

int main()
{
    fin >> A >> B;
    D=GCD(A, B);
    M=(A * B) / D;
    rest[0]=1;
    for (i=1; i<CIF; i++)
    {
        rest[i]=rest[i-1]*10;
        rest[i]%=M;
        if (rest[i]==0)
          rest[i]+=M;
    }
    prec[0]=1;
    K++;
    for (i=0; i<CIF; i++)
    {
        nr=K;
        if (prec[M-rest[i]]!=0)
        {
            prec[M]=M-rest[i]+1;
            app[M]=i;
            D=M;
            break;
        }
        for (j=1; j<=K; j++)
        {
            D=v[j]+rest[i];
            if (D>M)
              D-=M;
            if (prec[D]==0)
            {
                prec[D]=v[j]+1;
                v[++nr]=D;
                app[D]=i;
            }
            if (D==M)
            {
                ok=true;
                break;
            }
        }
        K=nr;
        if (ok==true)
          break;
    }
    while (D>0)
    {
        c[app[D]]=1;
        D=prec[D]-1;
    }
    for (i=app[M]; i>=0; i--)
      fout << c[i];
    fin.close();
    fout.close();
    return 0;
}