Cod sursa(job #2449905)

Utilizator mirceatlxhaha haha mirceatlx Data 21 august 2019 01:45:04
Problema GFact Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
 
ifstream fin("gfact.in");
ofstream fout("gfact.out");
 
vector <int> fact;
int num[1000];
 
int legendre(long long check, int prime)
{
    int number = 0;
    int copy = prime;
    while(prime <= check)
    {
        number = number + (check / prime);
        prime *= copy;
    }
 
    return number;
}
 
bool Check(long long check)
{
    int size = fact.size();
    int number;
    for(int i = 0 ; i < size ; i++)
    {
        if(legendre(check,fact[i]) < num[i])
            return false;
    }

    return true;
}

long long binarySearch()
{
    long long right = 1, left = 1, result, solution = -1;
    right = 2147483648;
    long long half;
    while(left <= right)
    {
        half = (right + left) / 2;
        if(Check(half) == true)
        {
            solution = half;
            right = half - 1;
        }
        else
        {
            left = half + 1;
        }
        
        
    }
    return solution;
}
 
void primeDecomposition(long long value, int exp)
{

    if(value % 2 == 0)
    {
        fact.push_back(2);
        int size = fact.size();
        while(value % 2 == 0)
        {
            num[size - 1]++;
            value /= 2;
        }
        num[size - 1] *= exp;
    }

    for(int i = 3 ; i * i <= value ; i += 2)
    {
        if(value % i == 0)
        {
            fact.push_back(i);
            int size = fact.size();
            while(value % i == 0)
            {
                num[size - 1]++;
                value /= i;
            }
            num[size - 1] *= exp;
        }
    }
    if(value > 1)
    {
        fact.push_back(value);
        num[fact.size() - 1] = exp;
    }
}
 

int main()
{
    int p,q;
    fin >> p >> q;
    if(p == 1)
    {
        fout << 1 << "\n";
        return 0;
    }
    primeDecomposition(p, q);
    fout << binarySearch() << "\n";
    return 0;
}