3027. 抽奖

IWani-Z

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;
}

Li Dao

直接模拟,判断互素最好的方法是最大公约数为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;
}

LzQuarter
#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个一组分成一组一组,每一组中有效的人数是固定的,剩下的就是数有几组人,还要多数几个人的问题
有一个小的细节是若恰好一个人都没多出来,需要倒回去一下,因为不知道上一组中的最后一个有效的人在哪

你当前正在回复 博客/题目
存在问题!