Untitled
unknown
plain_text
a month ago
1.6 kB
7
Indexable
Never
#include <bits/stdc++.h> #define endl "\n" #define ll long long #define sz(x) ((int) (x).size()) #define all(x) (x).begin(), (x).end() #define Y cout<<"YES"<<endl #define N cout<<"NO"<<endl #define int long long #define pb push_back #define ff first #define ss second #define vi vector<int> #define pii pair<int, int> #define rep(i, a, b) for(int i = (a); i < (b); i++) using namespace std; vector<int> primes; const int MAX = 100005; bool isPrime[2 * MAX + 1]; void sieve() { for (int i = 0; i < 2 * MAX + 1; i++) { isPrime[i] = true; } isPrime[0] = isPrime[1] = false; for (int i = 2; i <= sqrt(2 * MAX); i++) { if (isPrime[i]) { for (int j = i * i; j <= 2 * MAX; j += i) { isPrime[j] = false; } } } for (int i = 2; i < 2 * MAX + 1; i++) { if (isPrime[i]) { primes.push_back(i); } } } void solve () { int n,maxm=LLONG_MIN; cin>>n; unordered_map<int, int> mp; for (int i=0; i<n; i++) { int x; cin>>x; mp[x]++; maxm = max(x, maxm); } int ans=0; for (auto &[val, cnt]: mp) { int x=val; for (int &y: primes) { int find = x*y; if (find > maxm) break; if (mp.find(find)!=mp.end()) { ans += (cnt * mp[find]); } } } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t=1; cin>>t; sieve(); //for (int i=0; i<10; i++) cout << primes[i] << " "; while(t--) { solve (); } }