Cod sursa(job #1802760)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 10 noiembrie 2016 17:10:43
Problema Multiplu Scor 100
Compilator cpp Status done
Runda laborator_10i Marime 1.08 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MaxN 2000001
using namespace std;

FILE *IN,*OUT;

int A,B,GCD,LCM,Number[100],Start,End,Size=0;
bool MOD[MaxN];
struct Q
{
    int digit,mod,father;
}Queue[MaxN];
bool found=false;
int gcd(int a,int b)
{
    if(a%b==0)return b;
    else return gcd(b,a%b);
}
int main()
{
    IN=fopen("multiplu.in","r");
    OUT=fopen("multiplu.out","w");

    fscanf(IN,"%d%d",&A,&B);

    GCD=gcd(A,B);
    LCM=A*B/GCD;
    MOD[1]=true,Queue[1].digit=Queue[1].mod=Start=End=1;
   while(!found)
   {
        for(int i=0;i<=1;i++)
        {
            if(!MOD[(Queue[Start].mod*10+i)%LCM])
                 Queue[++End].digit=i,Queue[End].father=Start,Queue[End].mod=(Queue[Start].mod*10+i)%LCM,MOD[(Queue[Start].mod*10+i)%LCM]=true;
            if(Queue[End].mod==0)
                found=true;
        }
        Start++;
   }
   while(End!=0)
   {
       Number[++Size]=Queue[End].digit;
       End=Queue[End].father;
   }
   for(int i=Size;i>0;i--)
   fprintf(OUT,"%d",Number[i]);
}