AT_abc263_g.[ABC263G] Erasing Prime Pairs

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

黑板上写有 NN 种不同的整数。第 ii 种整数为 AiA_i,写了 BiB_i 个。

你可以尽可能多次地重复以下操作:

  • 从黑板上选择两个整数 x,yx, y,使得 x+yx+y 是素数。将这两个选中的整数从黑板上擦去。

请问最多可以进行多少次这样的操作。

输入格式

输入按以下格式从标准输入给出。

NN
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
ANA_N BNB_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    3
    3 3
    2 4
    6 2

    输出#1

    3
  • 输入#2

    1
    1 4

    输出#2

    2

说明/提示

限制条件

  • 1≤N≤1001 \leq N \leq 100
  • 1≤Ai≤1071 \leq A_i \leq 10^7
  • 1≤Bi≤1091 \leq B_i \leq 10^9
  • 所有 AiA_i 互不相同
  • 输入均为整数

样例解释 1

2+3=52+3=5,55 是素数,因此可以选择 22 和 33 并将其从黑板上擦去。除此之外无法进行其他操作。由于 22 有 44 个,33 有 33 个,所以可以进行 33 次操作。

样例解释 2

1+1=21+1=2,22 是素数,因此可以选择两个 11 并将其从黑板上擦去。由于 11 有 44 个,所以可以进行 22 次操作。

由 ChatGPT 4.1 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页