学步园

二分 + 容斥原理

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;


const int MAXN = 1000005;
const int inf  = 0x3f3f3f3f;
typedef long long ll;
bool is_prime[MAXN];
ll   prime[MAXN];
ll   factor[110], ans;
int  len, pcnt;
inline ll min(ll a, ll b) {
    return a < b ? a : b;
}
inline ll max(ll a, ll b) {
    return a > b ? a : b;
}
void Init() {
    int i, j;
    len = 0;
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    prime[len++] = 2;
    for(i = 4; i < MAXN; i += 2)
        is_prime[i] = false;
    for(i = 3; i * i <= MAXN; i += 2) {
        if(is_prime[i]) {
            prime[len++] = i;
            for(j = i * i; j < MAXN; j += i)
                is_prime[j] = false;
        }
    }
    for( ; i < MAXN; i += 2)
        if(is_prime[i])
            prime[len++] = i;
    return ;
}
void cal_factor(ll n) {
    pcnt = 0;
    for(int i = 0; i < len && prime[i] * prime[i] <= n; ++i) {
        if(n % prime[i] == 0) {
            factor[pcnt++] = prime[i];
            while(n % prime[i] == 0)
                n /= prime[i];
        }
    }
    if(n > 1) factor[pcnt++] = n;
    return ;
}
void dfs(int id, ll cur, int cnt, ll limit) {
    if(id == pcnt) {
        if(cnt & 1)
            ans -= limit / cur;
        else
            ans += limit / cur;
        return ;
    }
    dfs(id + 1, cur, cnt, limit);
    dfs(id + 1, cur * factor[id], cnt + 1, limit);
    return ;
}
ll get_num(ll limit) {
    ans = 0;
    dfs(0, 1, 0, limit);
    return ans;
}
ll solve(ll m, ll k) {
    ll ret = inf;
    cal_factor(m);
    int low = 1, high = inf, mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if(get_num(mid) >= k) {
            ret = min(ret, mid);
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return ret;
}
int main() {
    //freopen("aa.in", "r", stdin);
    ll m, k;
    Init();
    while(cin >> m >> k) {
        cout << solve(m, k) << endl;
    }
    return 0;
}