#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; }
将人按照m个一组分成一组一组，每一组中有效的人数是固定的，剩下的就是数有几组人，还要多数几个人的问题 有一个小的细节是若恰好一个人都没多出来，需要倒回去一下，因为不知道上一组中的最后一个有效的人在哪
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; }
直接模拟，判断互素最好的方法是最大公约数为1
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; }
将人按照m个一组分成一组一组，每一组中有效的人数是固定的，剩下的就是数有几组人，还要多数几个人的问题
有一个小的细节是若恰好一个人都没多出来，需要倒回去一下，因为不知道上一组中的最后一个有效的人在哪
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;
}
直接模拟，判断互素最好的方法是最大公约数为1
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;
}