Cod sursa(job #115242)

Utilizator mariusdrgdragus marius mariusdrg Data 16 decembrie 2007 11:47:10
Problema Multiplu Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 1.39 kb
#include<stdio.h>


const int maxn = 2000000;
const int maxn1 = 60000;

bool ver[maxn];
int n,m;
int i;
int mu;
int a[maxn1];
int b[maxn1];
bool sol;
int j;

int gcd(int i,int j)
{
        while(j)
        {
                int aux = j;
                j = i % j;
                i = aux;
        }
        return i;
}

int verif(int i)
{
        while(i)
        {
                if (i % 10 != 1 && i % 10 != 0) return false;
                i /= 10;
        }
        return true;
}

void bkt(int i,int r)
{
        if (ver[r]) return ;
        if (verif(r) && i != 1)
        {
                b[++b[0]] = r;
                sol = 1;
                return ;
        }
        ver[r] = 1;
        int j;
        for(j = 1;j <= 10; ++j)
        {
                if ((r + mu * j) % 10 == 0 || (r + mu * j) % 10 == 1)
                {
                        bkt(i + 1,(r + mu * j) / 10);
                        if (sol)
                        {
                                b[++b[0]] = (r + mu * j) % 10;
                                return ;
                        }
                }
        }
}


int main()
{
        freopen("multiplu.in","r",stdin);
        freopen("multiplu.out","w",stdout);
        scanf("%d %d",&n,&m);
        mu = n * m / gcd(n,m);
        bkt(1,0);

        for(i = 1;i <= b[0];++i)
        {
                printf("%d",b[i]);
        }
        printf("\n");

        return 0;
}