Cod sursa(job #2218994)

Utilizator dianamichesaRosu Diana Michesa dianamichesa Data 6 iulie 2018 18:01:48
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
const int N=2000001;
int a,b,u[N],pred[N],q[N],n,m;
int cmmmc(int a,int b){
    int r=a;
    int p=a,v=b;
    while(b){
        r=a%b;
        a=b;
        b=r;
    }
    return p/a*v;
}
void numar(int x){
    if(x!=1){
        numar(pred[x]);
        }
    g<<u[x];
}
int main()
{
    f>>n>>m;
    int k=cmmmc(n,m);
    for(int i=0;i<k;i++)
        u[i]=-1;
    u[1]=1;
    int st=0,dr=-1;
    q[++dr]=1;
    while(st<=dr){
        int x=q[st++];
        int y=x*10%k;
        if(u[y]==-1){
            u[y]=0;
            pred[y]=x;
            q[++dr]=y;
        }
        y=(x*10+1)%k;
        if(u[y]==-1){
            u[y]=1;
            pred[y]=x;
            q[++dr]=y;
        }
        if(u[0]!=-1)
            break;
    }
    numar(0);
    return 0;
}