8.14 模拟赛小结

前言

最喜欢的一集

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;
}