Cod sursa(job #2960015)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 3 ianuarie 2023 14:02:44
Problema Frac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<fstream>
#include<iostream>

using namespace std;

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

//ifstream f("in.in");
//ofstream g("out.out");

long long n,p;
long long d,k=0,v[105];
long long nr,i,cnt,prod,j;
long long st,dr,mid,solNr;

long long sol(long long m){

    nr = 0;cnt=0;
    ///generare
    for(i=1;i<(1<<k);i++){
        cnt=0;prod=1;
        for(j=0;j<k;j++){
            if(i&(1<<j)){
                prod*=v[j+1];
                cnt++;
            }
        }

        ///includere/excludere
        //cout<<"|"<<prod<<"|";
        if(cnt!=0){
            if(cnt%2 == 1){
                nr+=m/prod;
            }else{
                nr-=m/prod;
            }
        }

    }

    return m-nr;
}

int main(){

    f>>n>>p;

    d = 2;k=0;
    while(d*d<=n && n!=1){
        bool ok = 0;
        while(n%d == 0){
            ok=1;
            n/=d;
        }
        if(ok == 1){
            k++;
            v[k] = d;
        }
        d++;
    }
    if(n!=1){
        k++;
        v[k] = n;
    }

    st=1;
    dr=(1LL<<61);
    //solNr = -1;


    while(st<=dr){
        mid = (st+dr)/2;
        if(sol(mid) >= p){
            solNr = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    g<<solNr;
    return 0;
}