在线评测链接:P1118

题目内容

塔子哥是一个喜欢解决有趣问题的高中生。有一天，他和 n − 1 n-1 n−1 个同学来到学校的操场，他们一起围成了一个圆圈。塔子哥和他的同学们非常兴奋，因为他们要开始一个非常有趣的游戏。

这个游戏的规则非常简单：从 1 1 1开始报数，每次报数时，如果报到的数字是素数，那么这个人就会被淘汰出游戏。淘汰的人离开圆圈，留下来的人继续报数，直到只有一个人留下来为止。

塔子哥非常聪明，他知道如何用算法来解决这个问题。他开始思考如何计算最后留下来的人的编号，以便告诉他的同学们答案。

现在，塔子哥想请你帮助他计算最后留下来的同学的编号。你需要根据给定的 n n n ，计算出最后留下来的同学的编号是多少。

素数：只能被 1 1 1和自己整除的数。

输入描述

一个正整数 n n n。代表学生的人数。

1 ≤ n ≤ 1 0 4 1\leq n\leq 10^4 1≤n≤104

输出描述

一个正整数，代表最终留下来的学生编号。

样例

输入

3

输出

1

样例 2

输入

8

输出

4

思路

模拟

遇到素数就删除，否则就继续。直到还剩下一个数.输出这个数即可。

唯一需要关心的就是复杂度是否能过去?

第 10000 − 1 10000-1 10000−1个非素数是 11372 11372 11372 , 和 n n n 一个阶。如果每次 O ( n ) O(\sqrt{n}) O(n ​)地判素数 ， 总复杂度为 O ( n n ) < 1 e 8 O(n\sqrt{n}) < 1e8 O(nn ​)<1e8 , 可以过。

类似题目推荐

LeetCode

剑指 Offer 62. 圆圈中最后剩下的数字

CodeFun2000

P1268 2023.04.29-美团春招-第三题-酒王

代码

CPP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 根号判素数
bool is_Prime(int num){if (num <= 1) {return false;}for(int i=2;i<=num/i;i++){if(num%i==0) return false;}return true;
}
int main(){int n;cin>>n;vector<int> a(n,1);int cnt=n,cur=1;// 模拟while(cnt!=1){for(int i=0;i<n;i++){if(a[i]&&is_Prime(cur++)){a[i]=0;cnt--;}}}cout<<find(a.begin(),a.end(),1)-a.begin()+1<<endl;return 0;
}

python

import sys
input = lambda:sys.stdin.readline().strip()
# 根号判质数
def is_prime(n):if n == 1:return Falsei = 2while i <= n / i:if n % i == 0: return Falsei += 1return True
a = [x for x in range(1,int(input())+1)]
# 模拟
cur = 1
while len(a) != 1:lin = []for i in range(len(a)):if not is_prime(cur):lin.append(a[i])cur += 1a = lin
print(a[0])

Java

import java.util.Scanner;
import java.util.Vector;public class Main {static boolean isPrime(int x) { // 判断素数函数if (x <= 1) {return false;}for (int i = 2; i <= x / i; i++) {if (x % i == 0) {return false;}}return true;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();Vector<Integer> a = new Vector<>(); // 定义向量 a，用于存储每个人是否出局for (int i = 0; i < n; i++) {a.add(1); // 初始化所有人都未出局}int cur = 1, cnt = n;while (cnt != 1) {for (int i = 0; i < n; i++) {if (a.get(i) == 1 && isPrime(cur++)) { // 如果当前人未出局并且当前轮到的数为素数a.set(i, 0); // 标记当前人出局cnt--; // 更新剩余未出局的人数}}}System.out.println(a.indexOf(1) + 1); // 输出最后一个未出局的人的编号}
}

Go

package mainimport ("bufio""fmt""os"
)// 根号判质数
func isPrime(n int) bool {if n == 1 {return false}i := 2for i <= n/i {if n%i == 0 {return false}i++}return true
}func main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()n := 0fmt.Sscanf(scanner.Text(), "%d", &n)// 初始化a := make([]int, n)for i := 1; i <= n; i++ {a[i-1] = i}// 模拟cur := 1for len(a) > 1 {lin := make([]int, 0)for i := range a {if !isPrime(cur) {lin = append(lin, a[i])}cur++}a = lin}fmt.Println(a[0])
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {input += data;return;
});
process.stdin.on('end', () => {const lines = input.trim().split('\n');// 根号判质数function isPrime(n) {if (n === 1) {return false;}let i = 2;while (i <= n / i) {if (n % i === 0) {return false;}i++;}return true;}const n = parseInt(lines[0]);// 初始化const a = Array.from({ length: n }, (_, idx) => idx + 1);// 模拟let cur = 1;while (a.length !== 1) {const lin = [];for (let i = 0; i < a.length; i++) {if (!isPrime(cur)) {lin.push(a[i]);}cur++;}a.splice(0, a.length, ...lin);}console.log(a[0]);
});

本文链接：https://my.lmcjl.com/post/11771.html