Cod sursa(job #2328240)

Utilizator BotzkiBotzki Botzki Data 25 ianuarie 2019 15:43:29
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <cstdlib>
#include <queue>
#include <string>
#include <bitset>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int NMAX=2000000;
string s;
struct numar
{
    int uc, rest;
};
int resturi[NMAX+5];
int anterior[NMAX+5];
bitset<NMAX+5>cifra;// ultima cifrfa pt fiecare rest
int sol[NMAX+5];
queue <int>q;
bitset <NMAX+5>viz;
int cmmdc(int a, int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    int a, b, cm, n=0;
    fin>>a>>b;
    if(a*b==1)
    {
        fout<<"1"<<"\n";
        return 0;
    }
    //cm-cmmmc
    cm=(a*b)/cmmdc(a, b);
   anterior[1]=-1;
   cifra[1]=1;
   viz[1]=1;
   q.push(1);
   while(!q.empty())
   {
       //in coada bag toate resturile mai mici decat m;
       int nr;
       a=q.front();
       q.pop();
       for(int i=0;i<=1;i++)
       {
           nr=a*10+i;
           nr=nr%cm;
           if(viz[nr]==0)
           {
              viz[nr]=1;
              anterior[nr]=a;
              cifra[nr]=i;
              q.push(nr);
           }
           if(viz[0]==1)
           {
               //contruim solutia si iesim din program
              int uc=0;
               while(uc!=-1)
               {
                   sol[++n]=cifra[uc];
                   uc=anterior[uc];
               }
               for(int k=n;k>=1;k--)
                fout<<sol[k];
               fout<<"\n";
               return 0;
           }
       }

   }
    return 0;
}