Cod sursa(job #2436920)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 7 iulie 2019 17:18:34
Problema Frac Scor 10
Compilator c-32 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>

typedef long long LL;

char nonprime[10000005];
LL primes[10000005], factors[100];
int no_primes, no_factors;

void sieve(LL n, char* a, LL* primes, int* no_primes)
{
    LL i, j;
    *no_primes = 1;
    primes[1] = 2;
    for (i = 3; i*i <= n; i += 2)
        if (a[i] == 0)
        {
            (*no_primes)++;
            primes[*no_primes] = i;
            for (j = i+(i<<1); j*j <= n; j += (i<<1))
                a[j] = 1;
        }
}

void factorisation(LL n, LL* primes, int no_primes, LL* factors, int* no_factors)
{
    *no_factors = 0;
    int i = 1;
    while (n > 1)
    {
        if (primes[i] * primes[i] > n || i > no_primes)
        {
            factors[++(*no_factors)] = n;
            n = 1;
        }
        else if (n % primes[i] == 0)
        {
            factors[++(*no_factors)] = primes[i];
            while (n%primes[i] == 0)
                n /= primes[i];
        }
        i++;
    }
}

LL how_many_ireductibles(LL* factors, int no_factors, LL p)
{
    int i, j;
    LL sol = p;
    for (i = 1; i < (1 << no_factors); i++)
    {
        LL prod = 1;
        int count = 0;
        for (j = 0; j < no_factors; j++)
        {
            if ((i & (1<<j)) != 0)
            {
                prod *= factors[j+1];
                count++;
            }
        }
        if (count%2==0)
            sol += p/prod;
        else
            sol -= p/prod;
    }
    return sol;
}

LL query(LL n, LL p)
{
    LL st = 0, dr = n;
    factorisation(n, primes, no_primes, factors, &no_factors);

    while (st <= dr)
    {
        LL mid = (st+dr)/2;
        LL ans = how_many_ireductibles(factors, no_factors, mid);
        //printf("ans = %lld  mid = %lld\n", ans, mid);
        if (ans < p)
            st = mid+1;
        else
            dr = mid-1;
    }
    return st;
}

int main()
{
    FILE* f = fopen("frac.in", "r");
    FILE* g = fopen("frac.out", "w");

    LL n, p;
    fscanf(f, "%lld %lld", &n, &p);
    sieve(n, nonprime, primes, &no_primes);

    fprintf(g, "%lld", query(n, p));

    fclose(f);
    fclose(g);

    return 0;
}