Cod sursa(job #2872941)

Utilizator AswVwsACamburu Luca AswVwsA Data 18 martie 2022 10:26:40
Problema Frac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <vector>
#define int long long
using namespace std;
vector <int> d;

int nr(int med)
{
    int dim = (1 << d.size());
    int ans = 0;
    for (int i = 1; i < dim; i++)
    {
        int cnt = 0, prod = 1;
        for (int j = 0; (1LL << j) <= i; j++)
            if (i & (1LL << j))
        {
            cnt++;
            prod *= d[j];
        }
        if (cnt % 2 == 0)
            ans -= med / prod;
        else
            ans += med / prod;
    }
    return med - ans;
}
signed main()
{
    ifstream cin("frac.in");
    ofstream cout("frac.out");
    int p, n;
    cin >> n >> p;
    int dv = 2;
    while (dv * dv <= n)
    {
        if (n % dv == 0)
        {
            d.push_back(dv);
            while (n % dv == 0)
                n /= dv;
        }
        dv++;
    }
    if (n > 1)
        d.push_back(n);
    int st = 1, dr = (1LL << 61), med, sol = -1;
    while (st <= dr)
    {
        med = ((st + dr) >> 1);
        if (nr(med) >= p)
        {
            sol = med;
            dr = med - 1;
        }
        else
            st = med + 1;
    }
    cout << sol;
}