#G1085. [GESP202412 五级] 奇妙数字

[GESP202412 五级] 奇妙数字

[GESP202412 五级] 奇妙数字

题目描述

小杨认为一个数字 xx 是奇妙数字当且仅当 x=pax = p^a,其中 pp 为任意质数且 aa 为正整数。例如,8=238 = 2^3,所以 88 是奇妙数字,而 66 不是。

对于一个正整数 nn,小杨想要构建一个包含 mm 个奇妙数字的集合 {x1,x2,…,xm}\{x_1, x_2, \dots, x_m\},使其满足以下条件:

  • 集合中不包含相同的数字。
  • x1×x2×⋯×xmx_1 \times x_2 \times \dots \times x_m 是 nn 的因子(即 x1,x2,…,xmx_1, x_2, \dots, x_m 这 mm 个数字的乘积是 nn 的因子)。

小杨希望集合包含的奇妙数字尽可能多,请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

输入格式

第一行包含一个正整数 nn,含义如题面所示。

输出格式

输出一个正整数,代表满足条件的集合最多包含的奇妙数字个数。

样例 #1

样例输入 #1

128

样例输出 #1

3

样例解释

关于本样例,符合题意的一个包含 33 个奇妙数字的集合是 {2,4,8}\{2, 4, 8\}。首先,因为 2=212 = 2^1,4=224 = 2^2,8=238 = 2^3,所以 2,4,82, 4, 8 均为奇妙数字。同时,2×4×8=642 \times 4 \times 8 = 64 是 128128 的因子。

由于无法找到符合题意且同时包含 44 个奇妙数字的集合,因此本样例的答案为 33。

数据范围

子任务编号 数据点占比 nn
1 20% ≤10≤ 10
2 ≤1000≤ 1000
3 60% ≤1012≤ 10^{12}
  • 对于全部数据,保证有 2≤n≤10122 ≤ n ≤ 10^{12}。

时间限制:1.0 s。内存限制:512.0 MB。