【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=1n?i1?=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;
}