Cod sursa(job #1867939)

Utilizator priboiraduPriboi Radu Bogdan priboiradu Data 4 februarie 2017 14:04:55
Problema Multiplu Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <stdlib.h>

FILE *fin, *fout;

int val[2000000], ant[2000000], q[2000000];

int cmmmc( int a, int b ) {
    int cmmdc = a, r, bb = b;
    while ( bb > 0 ) {
        r = cmmdc % bb;
        cmmdc = bb;
        bb = r;
    }
    return a * b / cmmdc;
}

void scrie( int i ) {
    if ( i != 1 )
        scrie( ant[i] );
    fprintf( fout, "%d", val[i] );
}

int main() {
    int a, b, i, m, j;
    fin = fopen( "multiplu.in", "r" );
    fout = fopen( "multiplu.out", "w" );
    fscanf( fin, "%d%d", &a, &b );
    m = cmmmc( a, b );
    i = 0;
    j = 0;
    q[i] = 1;
    val[1] = 1;
    ant[1] = 0;
    q[j+1] = ( q[i] * 10 ) % m;
    val[q[j+1]] = 0;
    ant[q[j+1]] = q[i];
    j++;
    q[j+1] = ( q[i] * 10 + 1 ) % m;
    val[q[j+1]] = 1;
    ant[q[j+1]] = q[i];
    j++;
    i++;
    while ( q[j] != 0 ) {
        if ( ant[(q[i] * 10 ) % m] == 0 && ( q[i] * 10 ) % m != 1 ) {
            q[j+1] = ( q[i] * 10 ) % m;
            val[q[j+1]] = 0;
            ant[q[j+1]] = q[i];
            j++;
        }
        else
            i++;
        if ( q[j] != 0 && ant[( q[i] * 10 + 1 ) % m] == 0 && ( q[i] * 10 + 1 ) % m != 1 ) {
            q[j+1] = ( q[i] * 10 + 1 ) % m;
            val[q[j+1]] = 1;
            ant[q[j+1]] = q[i];
            j++;
            i++;
        }
        else
            i++;
    }
    scrie( 0 );
    fclose( fin );
    fclose( fout );
    return 0;
}