← 返回题目列表

AtCoder · ijpc_primehazard

B. 击败复合数(Prime Hazard)

中文机器翻译题面 查看原题

狐狸太郎和次郎正在玩一款名为 Prime Hazard 的电脑游戏。

Prime Hazard中出现的角色上写有大于2的整数,写有素数的角色是玩家的同伴,写有合数的角色是玩家的敌人。

玩家必须看着角色上写的数字,立即判断自己是敌人还是盟友,并只攻击敌人。输入写在敌人身上的数字的最小质因数即可击败敌人。

太郎和二郎在玩这个游戏时决定角色划分如下。

  • 太郎读取敌人的数量并将该信息转发给二郎。
  • 根据太郎提供的信息,二郎判断该角色是否是敌人,如果是,则最小质因数是多少。

由于我们必须一次处理大量字符,因此我们希望使信息通信尽可能简单。太郎决定告诉二郎一些数字,0或1。

課題

大于或等于 2 的正整数 判断N被给予。N是否是素数。对于合数,找到最小的质因数。

执行以下程序:

  • 具有以下参数的过程 芋头(N):
    • N -- 给定的正整数。
    在此过程中 发送(b) 通过重复调用 可以向Jiro发送数据。但是,b 必须为 0 或 1。此过程 二郎(S, X) 在 之前仅调用一次,并且没有返回值。
  • 具有以下参数的过程 二郎(S, X) 在:
    • S -- 从 Taro 发送的数据的长度(位数)。
    • X -- S 整数的一维数组。0 ≤ i < S 对于 反对 X[i] 是 它仅由 芋头(N) 里面 发送(b) 通过重复调用 是 在 i+1 被呼叫时 等于 b 的值。
    此程序 仅在调用 芋头(N) 后调用一次。这个程序如果 N 是质数,则为 -1;如果 N 是合数,则为最小质因数必须作为返回值返回。

例

例1

N = 7 考虑

的情况。

芋头 里面 发送 假设 被这样调用:

发送(1)
发送(1)
发送(0)
发送(1)

此时 二郎 通话中 S = 4 和

X =  1
1
0
1

变为。

在这种情况下,7 是质数,所以 必须返回二郎 是 它仅由 -1 。

例2

N = 6

的情况。

在这种情况下,6 是一个合数,最小的质因数是 2,所以 二郎 是 它仅由 2 。

小課題

小課題 1 (50 点)

  • 2 ≤ N ≤ 1 000
  • Taro 发送给 Jiro 的数据大小(S) 是 必须小于或等于 12 。

小課題 2 (50 点)

  • 2 ≤ N ≤ 1 000 000 000
  • Taro 发送给 Jiro 的数据大小(S) 是 必须小于或等于 12 。
 

实施细节

制限

  • CPU时间限制:1秒
  • 内存限制:64 MB
    注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。

接口 (API)

  • 实现文件夹:primehazard/(原型: primehazard.zip)
  • 参赛者实现的文件:primehazard.cpp
    注意: 请注意,虽然从提交的文件生成了一个可执行文件,但在判断服务器上启动了两个执行实例。特别是在使用全局或静态变量时。 请注意,您不能与芋头和二郎共享这些变量。
  • 提交文件接口:primehazard.h
  • 评分程序接口:grader.h
  • 评分程序示例:grader.cpp
  • 评分程序的示例输入:grader.in.1、grader.in.2、...
    注意:示例评分程序按以下格式读取输入。 写入
    • 1 行目: 整数 N 。N 表示给定的正整数。
  • 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
    注意:示例评分程序按以下格式写入输出。
    • 第 1 行:过程 写入 二郎 应返回的值。

  • 问题建议:qnighy
  • 问题陈述:utatakiyoshi