3220 问题 F: 蓝桥杯2024年第十五届省赛真题-因数计数

时间限制: 1s 内存限制: 256MB 提交: 1457 解决: 166
题目描述
小蓝随手写出了含有 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 互不相等。
输入
输入的第一行包含一个正整数 n 。第二行包含 n 个正整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔。
输出
输出一行包含一个整数表示答案。
样例输入
5
3 6 2 2 7
样例输出
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 。

#include<stdio.h>
int main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

比赛公告

请基地所有同学们认真做题，以后会每天发布一套蓝桥杯历年真题。积极备赛，争取省一。加油！

比赛状况