Cod sursa(job #2869761)

Utilizator sims_glAlexandru Simion sims_gl Data 11 martie 2022 20:11:38
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;
int i,viz[2000005], cif[2000005],a,b,I;
struct ij{
    int i;
    int j;
};
vector< ij> v;
queue <int > q;
long long gcd(long long int a, long long int b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
 long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    cin>>a>>b;
    int cm= lcm(a,b);
    q.push(1);
    int ok=1;
    while(!q.empty() && ok)
    {
        int r= q.front();
        q.pop();
        for(int i=0;i<=1;i++)
        {
            int x= (r*10+i)%cm;
            if(viz[x]==0)
            {
                viz[x]=r;
                cif[x]=i;
                q.push(x);
            }
            if(x==0)
            {
                I=x;
                ok=0;
            }
        }
    }
    while(I!=1)
    {
        cout<<cif[I];
        I=viz[I];
    }
    cout<<1;
}