题目描述
小蓝随手写出了含有 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 。
第一次代码：时间超限 27分
#include <bits/stdc++.h>
#define MX 100005
using namespace std;
int a[MX],b[MX] = {0};
int main() {
int n;
cin>>n;
for(int i = 1; i <= n; i++) {
cin>>a[i];
}
int cnt = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1;j <= n;j++){
for(int k = 1;k <= n;k++){
for(int l = 1;l <= n;l++){
if(i != j && i != k && i != l && j != k && j != l&& k != l &&a[k] % a[i] == 0 && a[l] % a[j] == 0)
{
cnt++;
}
}
}
}
}
cout<<cnt<<endl;
return 0;
}
第二次代码：好难！好难！好难！
#include <bits/stdc++.h>
#define MX 100005
using namespace std;
typedef __int128 ll;
int a[MX],b[MX] = {0};
ll f[MX],g[MX],cnt[MX] = {0};
void print128(ll x){
if(x > 9) print128(x / 10);
putchar(x % 10 + '0');
}
int main() {
int n,mx = 0;
cin>>n;
for(int i = 1; i <= n; i++) {
cin>>a[i];
cnt[a[i]]++;
mx = max(mx,a[i]);
}
for(int i = 1;i <= mx;i++)
{
for(int j = i;j <= mx;j = j + i)
{
f[i] += cnt[j];//记录i的倍数
g[j] += cnt[i]; //记录j的因子数
if(i == j) {
f[i]--;
g[i]--;
}
}
}
ll ant = 0;
//所有二元组
for(int i = 1;i <= mx;i++)
{
ant += cnt[i] * f[i];
}
//四元组:i != k && j != l && k != l && i != j
ant = ant * (ant - 1);
//减去i == j
for(int i = 1;i <= mx;i++)
{
ant = ant - cnt[i] * f[i] * (f[i] - 1);
ant = ant - cnt[i] * g[i] * (g[i] - 1);
ant = ant - cnt[i] * f[i] * g[i] * 2;
ant = ant + cnt[i] * (cnt[i] - 1);
}
print128(ant);
return 0;
}
