【16届蓝桥杯寒假刷题营】第2期DAY4
【16届蓝桥杯寒假刷题营】第2期DAY4 - 蓝桥云课
问题描述
幼儿园小班的浩楠同学有一个序列 a。
他想知道有多少个整数三元组 (i,j,k) 满足 1≤i,j,k≤n 且 ai×aj=ak。
输入格式
共2行，第一行一个整数 n，表示序列的长度。
第二行 n 个整数，表示序列的每一项。
输出格式
共一行，一个整数 ans，表示三元组的个数。
样例输入
5
2 3 4 5 6样例输出
3说明
满足条件的三元组有 (1,1,3), (1,2,5), (2,1,5)。
评测数据规模
对于100%的评测数据，1≤n≤1e5，1≤ai≤1e5。
思路：
这题n最大1e5。我们可以优化成mlogm。
考虑枚举 ai，aj，可以发现当 ai 很大时，如果想要 ai×aj 在 a 中出现，aj 必须很小。
下面证明这样枚举的时间复杂度时合理的：
根据调和级数 ∑i=1ni1=O(nlogn)。
设 m=105，那么满足 i×j≤m 的 (i,j) 至多只有 O(mlogm) 对。
记录每个元素出现的次数并统计即可。
时间复杂度 O(mlogm)。
代码如下：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
const ll M = 1e5;
ll n;
ll has[N];
ll sum;
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(ll i = 1 ; i <= n ; i++)
{
ll x;
cin >> x;
has[x]++;
}
//暴力枚举
for(ll i = 1 ; i <= M ; i++)
{
for(ll j = 1 ; i * j <= M ; j++)
{
sum += has[i]*has[j]*has[i*j];
}
}
cout << sum;
}