3032. 是坚挺数吗？

一共有112个坚挺数。
知道怎么做了吧……

一个简单的数学问题。

设数字当前的位置是 $n$，当前是第 $k$ 轮淘汰，那么有如下三种情况：

1. 如果 $n < k$，那么 $n$ 再也不可能被淘汰了，所以它是一个坚挺数。
2. 如果 $n \mod k = 0$，那么 n 就在这一轮被淘汰了，所以它不够坚挺。
3. 如果前两种情况都不能判断，说明 $n$ 暂时幸存了下来，它的新位置是 $n - \lfloor \frac{n}{2}\rfloor$，这是因为在它前面有 $\lfloor \frac{n}{2}\rfloor$ 个数在这一轮中被淘汰掉了。返回 1，直到得出结论。

那么写出代码就是 trivial 的了。

#include "bits/stdc++.h"
using namespace std;

uint32_t is_firm(uint32_t num, uint32_t div = 2) {
    assert(num > 0 && div >= 2);
    if (num < div)
        return num;
    else if (num % div == 0)
        return 0;
    else
        return is_firm(num - num / div, div + 1);
}

int main() {
    uint32_t t; cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        printf("case #%u:\n", query);
        if (uint32_t n, check; cin >> n, check = is_firm(n))
            printf("Yes %u\n", check);
        else
            puts("No");
    }
}

include

include

eoj是真的快！！我先创造出坚挺数数组，也就是模拟隔i个数字移除的操作，大概500000个原始数，再移除个500次就够用了，也不会超时，大概是最笨的方法了，注意iterator的使用，不要越界了
using namespace std;
int main() {
list nums;
for (int i = 1; i <= 500000; i++) {
nums.push_back(i);
}
int flag = 0;
for (int i = 1; i < 500; i++) {
list::iterator iter = nums.begin();
flag = 0;
while (true) {
for (int k = 1; k <= i; k++) {
if (iter == nums.back()) {
flag = 1;
break;
}
iter++;
}
if (iter == nums.back()) {
nums.erase(iter);
break;
}
iter = nums.erase(iter);
}
}
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n;
cin >> n;
list::iterator iter = nums.begin();
int cnt = 1;
printf(“case #%d:\n”, i);
for (; iter != nums.end(); iter++) {
if (iter == n) {
cout << “Yes “;
printf(“%d\n”, cnt);
break;
}
if (iter > n) {
cout << “NO” << endl;
break;
}
cnt++;
}
}
}

n = int(input())
for i in range(n):
print(“case #%d:”%i)
s = int(input())
t = 1
while s >= t:
t = t + 1
if s % t == 0:
print(“No”)
a = 0
break
else:
s = s - s // t
a = 1
if a:
print(“Yes”,s)