Cod sursa(job #1879664)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 15 februarie 2017 08:41:22
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
vector <bool>v;
queue <int>Q;
const int Nmax=2000000+5;
int dp[Nmax];
bool ok=0;
bool cif[Nmax];
int a,b,c;
void verif(int r)
{
    if(dp[(r*10)%c]==0){
    Q.push((r*10)%c);
    dp[(r*10)%c]=r;
    cif[(r*10)%c]=0;
    }
    if(dp[(r*10+1)%c]==0){
    Q.push((r*10+1)%c);
    dp[(r*10+1)%c]=r;
    cif[(r*10+1)%c]=1;
    }
}
int cmmdc(int x,int y)
{
    int r;
    while(y!=0)
    {
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}
int main()
{
    fin>>a>>b;
    c=(a*b)/cmmdc(a,b);
    Q.push(1);
    dp[1]=1;
    int r=0;
    while(!Q.empty() && ok==0){
    r=Q.front();
    Q.pop();
    if(r==0)
    {
        ok=1;
        while(r!=1)
        {
            v.push_back(cif[r]);
            r=dp[r];
        }
    v.push_back(1);
    if(v.size()!=0)for(int i=v.size()-1;i>=0;--i)fout<<v[i];
    }
    else verif(r);
    }
    return 0;
}