Cod sursa(job #1725162)

Utilizator Bodo171Bogdan Pop Bodo171 Data 5 iulie 2016 00:41:01
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include<fstream>
#include<bitset>
#include<queue>
using namespace std;
char str[2000005];
int prec[200005],a,b,n,p,rest,x,i,k;
bitset<2000005> cf,dist;
queue<int> q;
int main()
{
    ifstream f("multiplu.in");
    ofstream g("multiplu.out");
    f>>a>>b;p=a*b;
    while(a!=b)
    {
        if(a>b) a-=b;
        else b-=a;
    }
    n=p/a;
    dist[1]=1;
    q.push(1);
    cf[1]=1;
    prec[1]=-1;
    while(dist[0]==0)
    {
        rest=q.front();
        q.pop();
        for(i=0;i<=1;i++)
        {
            x=(rest*10+i)%n;
            if(dist[x]==0)
            {
                dist[x]=1;
                cf[x]=i;
                prec[x]=rest;
                q.push(x);
            }
        }
    }
    x=0;
    while(x!=-1)
    {
        k++;
        str[k]=cf[x]+'0';
        x=prec[x];
    }
    for(k;k>0;k--)
        g<<str[k];
    return 0;
}