1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include<cstdio>
long long num,l,r,m;
long long n,t=1,tot,cnt;
long long arr[10];
bool vis[10];
void dfs(int n,int l,long long va,long long mx){
	if(n==0){
		cnt+=mx/va;
		return;
	}
	for(int i=l+1;i<t;i++){
		if(vis[i])continue;
		vis[i]=1;
		dfs(n-1,i,va*arr[i],mx);
		vis[i]=0;
	}
}
int check(long long k){
	tot=0;
	for(int i=1;i<t;i++){
		cnt=0;
		dfs(i,0,1,k);
		tot+=((i&1)?cnt:-cnt);
	}
	tot=k-tot;
	return tot>=num;
}
int main(){
	while(scanf("%lld%lld",&n,&num)!=EOF){
		t=1;
		if(!(n&1)){
			arr[t++]=2;
			while(!(n&1))
				n>>=1;
		}
		for(long long i=3;i*i<=n;i+=2)
			if(n%i==0){
				while(n%i==0)
					n/=i;
				arr[t++]=i;
			}
		if(n!=1)
			arr[t++]=n;
		l=0;r=1e10;
		while(l<r){
			m=(l+r)/2;
			if(check(m))r=m;
			else l=m+1;
		}
		printf("%lld\n",l);
	}
	return 0;
}