# 3027. 抽奖

### include

using namespace std;

int main(){
int num,n,k,i,j,a,b,t;
int no = 0;
cin >> num;
while(num–){
cin >> n >> k;
for(i = 1, j = 2; i < k; j++){
a = j;
b = n;
while(a != 0){
t = a;
a = b % a;
b = t;
}
if(b == 1)
i++;
}
printf(“case #%d:\n%d\n”,no++,–j);
}
return 0;
}

### include

using namespace std;
int T;
int gcd(int aa,int bb)
{
if(aa>m>>n;
int i=1,cnt=0;
while(cnt<n)
{
while(gcd(i,m)!=1) i++;
cnt++;i++;
}
cout<<i-1<<endl;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

#include<iostream>
using namespace std;
int gcd(int a, int b){
return a % b == 0 ? b : gcd(b, a % b);
}
int main(){
int T;
cin >> T;
for(int t = 0; t < T; t++){
cout << "case #" << t << ":" << endl;
int m, n;
cin >> m >> n;
int left = 0;
int arr[50001] = {0};
for(int i = 1; i <= m; i++){
if(gcd(i, m) == 1){
arr[i] = 1;
left++;
}
}
int sections = n / left;
int addition = n % left;
if(addition == 0){
sections -= 1;
addition = left;
}
int trueaddition = 0;
while(addition){
if(arr[trueaddition]){
addition--;
if(!addition){
break;
}
}
trueaddition++;
}
cout << m * sections + trueaddition << endl;
}
return 0;
}