容斥原理求第k个与n互质的数。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
vector<int> v;
void init(int n) {
v.clear();
for(int i = ; i*i<=n; i++) {
if(n%i==) {
v.pb(i);
}
while(n%i==)
n/=i;
}
if(n!=)
v.pb(n);
}
ll solve(ll x) {
int len = v.size();
ll ret = ;
for(int i = ; i<(<<len); i++) {
ll cnt = , ans = ;
for(int j = ; j<len; j++) {
if((<<j)&i) {
cnt++;
ans *= v[j];
}
}
if(cnt&) {
ret += x/ans;
} else {
ret -= x/ans;
}
}
return x-ret;
}
int main()
{
int n, m;
while(cin>>n>>m) {
init(n);
ll l = , r = 1LL<<, ans;
while(r>=l) {
ll mid = (l+r)/;
ll ret = solve(mid);
if(ret>=m)
r = mid-1;else
l = mid+;
}
cout<<l<<endl;
}
return ;
}