Cod sursa(job #1870129)

Utilizator giotoPopescu Ioan gioto Data 6 februarie 2017 13:46:26
Problema Frac Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int NR, CR = 0;
long long Sol, mij, Prod, n, m, divi[1000];
inline void back(int k){
    if(k == NR){
        if(Prod == 1) return ;
        for(int i = 1; i <= NR ; ++i)
            if(Prod == divi[i]) return ;
        Sol = Sol + mij / Prod;
        return ;
    }
    back(k + 1);
    Prod *= divi[k + 1];
    back(k + 1);
    Prod /= divi[k + 1];
}
int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    NR = 0;
    if(n % 2 == 0){
        while(n % 2 == 0) n = n / 2;
        divi[++NR] = 2;
    }
    long long d = 3, rad = sqrt(n);
    while(d < rad){
        if(n % d == 0){
            divi[++NR] = d;
            while(n % d == 0) n = n / d;
            rad = sqrt(n);
        }
        d += 2;
    }
    if(n > 1) divi[++NR] = n;
    long long afis, st = m, dr = (long long)((long long)1 << 61);
    while(st <= dr){
        mij = (st + dr) / 2;
        Sol = mij;
        for(int i = 1; i <= NR ; ++i)
            Sol = Sol - mij / divi[i];
        Prod = 1; CR = 0;
        back(0);
        if(Sol >= m){
            dr = mij - 1;
        }
        else if(Sol < m) st = mij + 1;
    }
    printf("%lld", st);
    return 0;
}