3032. 是坚挺数吗?

Master X

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

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$ 轮淘汰,那么有如下三种情况:

  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");
    }
}
wty403

新位置是n-n//k,不是n-n//2(我猜是笔误)

Deuchie

的确是写错啦,谢谢纠正~

wty403

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)

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