Cod sursa(job #2582416)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 16 martie 2020 18:24:04
Problema Frac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

const int MAXN = 1e7 + 1;

using namespace std;

ifstream in("frac.in");
ofstream out("frac.out");

typedef long long ll;

bool ciur[MAXN];
ll prime[MAXN];
int index;
vector<ll>divs;
ll pozitie,n;

void construieste_ciur(int valmax){
    prime[++index] = 2;
    for(ll i = 3; i <= valmax; i += 2){
        if(!ciur[i]){
            prime[++index] = i;
            for(ll j = i * i; j <= valmax; j += i)
                ciur[j] = true;
        }
    }

}
void construieste_divizori(ll n){
    ll d = 2;
    int index = 1,exp;
    while(d * d <= n){
        exp = 0;
        while(n % d == 0){
            n /= d;
            exp++;
        }
        if(exp)
            divs.emplace_back(d);
        index++;
        d = prime[index];
    }
    if(n > 1)
        divs.emplace_back(n);
}
bool ok(ll numar){
    int maxim = divs.size();
    ll ans = 0;
    for(int i = 1; i < (1<<maxim); ++i){
        ll prod = 1;
        int cnt = 0;
        for(int j = 0; j < maxim; ++j){
            if((i & (1<<j)) > 0){
                prod *= divs[j];
                cnt++;
            }
        }
        if(cnt & 1)
            ans += numar / prod;
        else
            ans -= numar / prod;
    }

    if(numar - ans < pozitie)
        return true;
    if(numar - ans == pozitie && __gcd(numar,n) == 1)
        return true;
    return false;
}
ll cautbinar(){
    ll pas = 1ll<<61, r = 0;
    while(pas){
        if(ok(r + pas))
            r += pas;
        pas /= 2;
    }
    return r;
}

int main()
{

    in>>n>>pozitie;
    construieste_ciur(sqrt(n));
    construieste_divizori(n);
    out<<cautbinar();

    return 0;
}