Cod sursa(job #2065969)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 14 noiembrie 2017 16:27:00
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <queue>
#define x first
#define y second
#define MAX 2000001

using namespace std;

int a,b,c;
bool acc[MAX];
queue<pair<int,string>> q;
int gcd(int t1,int t2){
  int r;
  do{
    r=t1%t2;
    t1=t2;
    t2=r;
  }while(t2!=0);
  return t1;
}

int main()
{
    ifstream f ("multiplu.in");
    ofstream g ("multiplu.out");
    f>>a>>b;
    if(a==b&&a==1){
      g<<1;
      return 0;
    } else {
      c=a*b/gcd(a,b);
      acc[1]=true;
      q.push(make_pair(1,"1"));
      while(true){
        pair<int,string> ac=q.front();q.pop();
        int r1=ac.x*10,r2=ac.x*10+1;
        r1%=c,r2%=c;
        if(r1==0){
          g<<ac.y+"0";
          return 0;
        }
        if(r2==0){
          g<<ac.y+"1";
          return 0;
        }
        if(not acc[r1])q.push(make_pair(r1,ac.y+"0")),acc[r1]=true;
        if(not acc[r2])q.push(make_pair(r2,ac.y+"1")),acc[r2]=true;
      }
    }
    f.close ();
    g.close ();
    return 0;
}