一共有112个坚挺数。
知道怎么做了吧……
#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;
}
一个简单的数学问题。
设数字当前的位置是 $n$,当前是第 $k$ 轮淘汰,那么有如下三种情况:
n
就在这一轮被淘汰了,所以它不够坚挺。那么写出代码就是 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(我猜是笔误)
的确是写错啦,谢谢纠正~