Cod sursa(job #2711832)

Utilizator Horis21Horia Radu Horis21 Data 24 februarie 2021 19:03:16
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#define V 2000000

using namespace std;

queue<pair<int,int>> q;
stack <int> s;

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

bool v[V];

int gcd(int a, int b)
{
    if (b == 0) return a;
	return gcd(b, a % b);
}

void bkt(int pos)
{
    while(pos)
    {
        s.push(pos%2);
        pos/=2;
    }
    while(!s.empty())
    {
        out << s.top();
        s.pop();
    }
}

int main()
{
    int a,b,scm;
    in >> a >> b;
    scm=(a*b)/gcd(a,b);
    q.push({1,1});
    while(!q.empty())
    {
        int pos=q.front().second;
        int r=q.front().first;
        q.pop();
        if(r==0)
        {
            bkt(pos);
            return 0;
        }
        if (v[1LL*r*10%scm]==0){v[1LL*r*10%scm]=1;q.push({1LL*r*10%scm,pos*2});}
        if (v[(1LL*r*10+1)%scm]==0){v[(1LL*r*10+1)%scm]=1;q.push({(1LL*r*10+1)%scm,pos*2+1});}
    }
    return 0;
}