Cod sursa(job #1878631)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 14 februarie 2017 12:31:04
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 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 cif[Nmax];
int a,b,c;
void bfs()
{
    int r;
    r=Q.front();
    Q.pop();
    if((r*10)%c==0)
    {
        dp[0]=r;
        cif[0]=0;
        return;
    }
    else
    {
        if(dp[(r*10)%c]==0){
        Q.push((r*10)%c);
        dp[(r*10)%c]=r;
        cif[(r*10)%c]=0;
        }
    }
    if((r*10+1)%c==0)
    {
        dp[0]=r;
        cif[0]=1;
        return;
    }
    else
    {
        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;
        }
    }
    bfs();
}
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);
    bfs();
    int r=0;
    while(r!=1)
    {
        v.push_back(cif[r]);
        r=dp[r];
    }
    v.push_back(1);
    for(int i=v.size()-1;i>=0;--i)fout<<v[i];
    return 0;
}