Problem 4089 --F: 因数计数

4089: F: 因数计数

上一题 正确率: $100.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

小蓝随手写出了含有 n 个正整数的数组 {a1, a2, · · · , an} ，他发现可以轻松 地算出有多少个有序二元组 (i, j) 满足 aj 是 ai 的一个因数。因此他定义一个整 数对 (x1, y1) 是一个整数对 (x2, y2) 的“因数”当且仅当 x1 和 y1 分别是 x2 和 y2 的因数。他想知道有多少个有序四元组 (i, j, k, l) 满足 (ai , aj) 是 (ak , al) 的因数， 其中 i, j, k, l 互不相等。

Input

输入的第一行包含一个正整数 n 。 

第二行包含 n 个正整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔。

Output

输出一行包含一个整数表示答案。 

Sample Input复制

5
3 6 2 2 7

Sample Output复制

4

提示

四元组 (1, 4, 2, 3) ：(3, 2) 为 (6, 2) 的因子；四元组 (1, 3, 2, 4) ：(3, 2) 为 (6, 2) 的因子；四元组 (4, 1, 3, 2) ：(2, 3) 为 (2, 6) 的因子；四元组 (3, 1, 4, 2) ：(2, 3) 为 (2, 6) 的因子。 

【评测用例规模与约定】

对于 20% 的评测用例，n ≤ 50 ； 对于 40% 的评测用例，n ≤ 104 ； 对于所有评测用例，1 ≤ n ≤ 105 ，1 ≤ ai ≤ 105 。

推荐代码 查看4089 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$7 $ms] Andyqian7 1095848 2024-04-17 10:31:42
内存最少[$4316 $KB] Andyqian7 1095848 2024-04-17 10:31:42
第一AC Andyqian7 1095848 2024-04-17 10:31:42
第一挑战 Andyqian7 1095848 2024-04-17 10:31:42

赛题来源/所属竞赛 第十五届蓝桥杯大赛软件赛省赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛