https://atcoder.jp/contests/abc249/tasks/abc249_d
题目大意:
给定n个数字,问我们能够满足Ai/Aj==Ak的数量有多少?
i,j,k只需要在下标的范围内即可,无硬性要求。
Sample Input 1
3
6 2 3
Sample Output 1
2
(i,j,k)=(1,2,3),(1,3,2) satisfy the conditions.
Sample Input 2
1
2
Sample Output 2
0
Sample Input 3
10
1 3 2 4 6 8 2 2 3 7
Sample Output 3
62
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
LL a[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
LL n;
cin>>n;
map<LL,LL> mp;
LL maxn=0;
for(LL i=1;i<=n;i++)
{
cin>>a[i];
maxn=max(maxn,a[i]);
mp[a[i]]++;
}
LL res=0;
for(LL i=1;i<=maxn;i++)//从小到大枚举出现过的数字
{
for(LL j=1;j*i<=maxn;j++)//然后倍增,把所有可以乘起来且有结果的数量加起来
{
LL k=i*j;
res+=mp[i]*mp[j]*mp[k];
//Ai/Aj==Ak可以相应的转化成Ai*Aj==Ak
//这样我们直接计算彼此的乘积即为答案
}
}
cout<<res<<endl;
mp.clear();
}
return 0;
}
标签:Index,Trio,ABC,LL,cin,Sample,maxn,Output,Input
From: https://www.cnblogs.com/Vivian-0918/p/16755333.html