一共有112个坚挺数。
知道怎么做了吧……
3032. 是坚挺数吗？
Saitama
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector <int> a(10001);
for(int i = 1; i < 10001; i++)
a[i] = i;
for(int j = 2; j < 113; j++)
{
for(int i = 1; i < a.size(); i++)
{
if(i % j == 0)
a[i] = -1;
}
for(int i = 1; i < a.size(); i++)
if(a[i] == -1)
a.erase(a.begin() + i);
}
int flag = 0;
for(int i = 1; i < a.size(); i++)
if(n == a[i])
{
flag = 1;
cout << "Yes " << i << endl;
break;
}
if(flag == 0)
cout << "No" << endl;
}
int main()
{
int T;
cin >> T;
for(int i = 0; i < T; i++)
{
printf("case #%d:\n", i);
solve();
}
return 0;
}
Deuchie
一个简单的数学问题。
设数字当前的位置是 $n$，当前是第 $k$ 轮淘汰，那么有如下三种情况：
- 如果 $n < k$，那么 $n$ 再也不可能被淘汰了，所以它是一个坚挺数。
- 如果 $n \mod k = 0$，那么
n就在这一轮被淘汰了，所以它不够坚挺。 - 如果前两种情况都不能判断，说明 $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");
}
}
新位置是n-n//k，不是n-n//2（我猜是笔误）
的确是写错啦，谢谢纠正~