传统题 1000ms 256MiB

Xhh的难题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

之前的比赛大家了解到鹿鸣被Red_Comet给难住了,鹿鸣不服气,为了找回面子也给Red_Comet出了一道题,用脚趾头想都知道Red_Comet肯定不会,他想请你帮他解决这个问题,你能帮他解决吗?

有两种操作:

  1. 从所有正整数中任选一个数字x(2x) x(2\leq x ),并将所有数字全部对x x 求余。
  2. 从这n n 个数字中任选一些数字,使得它们全部减去一。

问最少进行多少次操作可以让所有数字全部变为 00

这两种操作都需要“任选”。

输入描述

第一行一个正整数n(1n1000001\le n \le100000)。

第二行给n个数字,第i个数字记作aia_i(0ai1090\le a_i \le10^9)

输出描述

一行一个整数,表示最少操作次数。

样例

输入

5
1 3 0 12 10

输出

2

样例解释

选择x=3x=3,先将所有数字对 3 求余,此时数组变为 [1,0,0,0,1],再选择第一个数字和第五个数字减一,共两次操作可以使得所有数字全部变为 0。

2022ACM新生积分赛 Round #5

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2022-11-12 13:10
结束于
2022-11-12 18:10
持续时间
5 小时
主持人
参赛人数
48