#P3520. Dzy loves chemistry 1

    ID: 2735 传统题 2000ms 512MiB 尝试: 250 已通过: 36 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举数论线性筛最小质因子预处理排序与序列处理一维前缀和数值计算与优化有理数精确运算随机化与近似随机哈希数据结构哈希表逆元线性递推CF2300By

Dzy loves chemistry 1

Dzy loves chemistry 1

题目描述

Dzy 在实验室找到一种有机酸。每个酸分子最多可以逐步电离出 n−1n-1 个氢离子,第 ii 步的电离常数是 KiK_i。他将 1 mol1\,\mathrm{mol} 这种酸溶于水,并可以调节溶液的氢离子浓度,使其取任意正值。

一种含碳粒子由它已经电离出的氢离子数确定。未电离的酸分子也计入,因此共有 nn 种需要考虑的含碳粒子。可以选择一个氢离子浓度,使其中若干种粒子的浓度都相等。求这些浓度相等的粒子种类数的最大值。

输入格式

第一行有一个整数 nn。接下来 n−1n-1 行,第 i+1i+1 行有一个整数 KiK_i,表示第 ii 步电离常数。

输出格式

一行一个整数,表示最多能使多少种含碳粒子的浓度相等。

样例 #1

4
2
2
2
4

取氢离子浓度为 22,相邻两个电离程度的粒子浓度相等,所以四种粒子的浓度都相等。

数据范围

1≤n≤10001\le n\le1000,1≤Ki≤1051\le K_i\le10^5。本题有 55 个测试点。