2021牛客暑期多校训练营7 H. xay loves count（枚举）

链接：https://ac.nowcoder.com/acm/contest/11258/H
来源：牛客网

题目描述

xay has an array a of length n, he wants to know how many triples (i, j, k) satisfy ai×aj=akai×aj=ak。

输入描述:

The first line of input contains an integer n（1≤n≤1061≤n≤106）.

The second line of input contains n integers a1,a2,⋯ ,ana1,a2,⋯,an（1≤ai≤1061≤ai≤106）.

输出描述:

Print a single integer, indicates the number of triples.

示例1

输入

复制

3
1 1 1

输出

复制

27

示例2

输入

复制

5
1 2 4 8 16

输出

复制

15

看到每个数的范围不大，考虑用桶来存储。然后遍历每个a[i]，枚举它的因子计算贡献即可。注意这个题的i, j, k可以相同也可以无序，因此(2, 1, 2)以及(1, 2, 2)算不同的两个三元组。

#include <bits/stdc++.h>
using namespace std;
int n, a[1000005], cnt[1000005];
//没说i, j, k不能相等
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		cnt[a[i]]++;
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		if(cnt[a[i]]) {
			for(int j = 1; j * j <= a[i]; j++) {//枚举因子
				if(a[i] % j != 0) continue; 
				if(j * j == a[i]) {
					if(cnt[j]) {
						ans += 1ll * cnt[j] * (cnt[j] - 1) + 1ll * cnt[j];//分别为值为j的两个数从不同位置拿，两个数从同一个位置拿
					}
				} else {
					ans += 2 * cnt[j] * cnt[a[i] / j];//乘法原理，相当于从两个因子桶分别拿一个的方案。*2是因为这两个数有两种排列方式
				}
			}
		}
 	}
 	cout << ans;
}