Cod sursa(job #2065972)

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

using namespace std;

int a,b,c,ra[MAX];
bool uc[MAX];
string nr;
queue<int> q;
vector<int> ansf;
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);
      ra[1]=1;uc[1]=1;
      q.push(1);
      while(true){
        int ac=q.front();q.pop();
        int r1=ac*10,r2=ac*10+1;
        r1%=c,r2%=c;
        if(r1==0){
          ra[0]=ac;
          uc[0]=0;
          break;
        }
        if(r2==0){
          ra[0]=ac;
          uc[0]=1;
          break;
        }
        if(not ra[r1])q.push(r1),ra[r1]=ac,uc[r1]=0;
        if(not ra[r2])q.push(r2),ra[r2]=ac,uc[r2]=1;
      }
      for(int i=0;i!=1;i=ra[i])ansf.push_back(uc[i]); ansf.push_back(1);
      for(int i=ansf.size()-1;i>=0;i--)g<<ansf[i];
    }
    f.close ();
    g.close ();
    return 0;
}