前言
最喜欢的一集
T1 儒略历
题意化简：给你一个长度为 \(n\) 的序列 需要挑选 \(4\) 个数 下标为\(A,B,C,D\)，满足
- \(A<B<C<D\)
- \(A\times B\times C=D\)
- \(n\leq 10^4\)
这个很简单 枚举 \(C\) 预处理 \(A*B\) 再枚举 \(D\) 时间复杂度 \(O(n^2)\) 能过
Code
#include<bits/stdc++.h>
#define N 10005
#define M 1000005
#define ll long long
using namespace std;
int n,sum[M],cnt[M];
int a[N];
ll ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
if(a[j]%a[i]==0) ans+=1ll*cnt[a[j]/a[i]];
for(int j=1;j<i;j++)
if(1ll*a[j]*a[i]<=1000000)cnt[a[j]*a[i]]++;
}
cout<<ans;
return 0;
}