同样是欧拉函数的基本应用。
$\phi (N)$表示$[1,N]$中，$gcd(i,N)==1$的数的个数，同理，其也能表示$[K \times N+1,(K+1) \times N]$中$gcd(i,N)==1$的数的个数，所有这样就能把区间固定下来，然后对于固定的区间扫一遍就行了。
//POJ 2773
//by Cydiater
//2016.10.8
#include <iostream>
#include <iomanip>
#include <cstring>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define down(i,j,n) for(ll i=j;i>=n;i--)
const int MAXN=1e6+5;
const int LIM=1e6;
const int oo=0x3f3f3f3f;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll phi[MAXN],cnt=0,prime[MAXN],N,K,leftt,rightt;
bool vis[MAXN];
namespace solution{
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
void pret(){
phi[1]=1;
memset(vis,0,sizeof(vis));
up(i,2,LIM){
if(!vis[i]){prime[++cnt]=i;phi[i]=i-1;}
up(j,1,cnt){
if(prime[j]*i>LIM)break;
vis[prime[j]*i]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
void slove(){
ll PHI=phi[N],tol=0;
leftt=(K-1)/PHI*N+1;rightt=leftt+N-1;
K-=(K-1)/PHI*PHI;
up(i,leftt,rightt){
if(gcd(i,N)==1)tol++;
if(tol==K){
printf("%lld\n",i);
return;
}
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
pret();
while(scanf("%lld %lld",&N,&K)!=EOF)slove();
return 0;
}