Cod sursa(job #2663230)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 25 octombrie 2020 17:21:50
Problema GFact Scor 60
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#define DMAX 45000
int ciur[DMAX + 1], d[DMAX];
long long caut_exp( int div, int exp ) {
    long long st, dr, mij, pd;
    int f;
    st = 0;
    dr = (long long)exp * div;
    while ( dr - st > 1 ) {
        mij = (st + dr) / 2;
        pd = div;
        f = 0;
        while ( pd <= mij ) {
            f += mij / pd;
            pd *= div;
        }
        if ( f < exp )
            st = mij;
        else
            dr = mij;
    }
    return dr;
}
int main() {
    FILE *fin, *fout;
    int p, q, np, e, i, j;
    long long exp, b;
    np = 0;
    for ( i = 2; i <= DMAX; i++ ) {
        if ( ciur[i] == 0 ) {
            d[np] = i;
            np++;
            for ( j = i * i; j <= DMAX; j += i )
                ciur[i] = 1;
        }
    }
    fin = fopen( "gfact.in", "r" );
    fscanf( fin, "%d%d", &p, &q );
    fclose( fin );
    b = 1;
    i = 0;
    while ( p > 1 && d[i] * d[i] <= p ) {
        e = 0;
        while ( p % d[i] == 0 ) {
            p /= d[i];
            e++;
        }
        e *= q;
        if ( e > 0 ) {
            exp = caut_exp( d[i], e );
            if ( exp > b )
                b = exp;
        }
        i++;
    }
    if ( p > 1 ) {
        exp = caut_exp( d[i], q );
        if ( exp > b )
            b = exp;
    }
    fout = fopen( "gfact.out", "w" );
    fprintf( fout, "%lld ", b );
    fclose( fout );
    return 0;
}