You are given $n$ positive integers $a_1, \ldots, a_n$, and an integer $k \geq 2$. Count the number of pairs $i, j$ such that $1 \leq i < j \leq n$, and there exists an integer $x$ such that $a_i \cdot a_j = x^k$.
Input
The first line contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $2 \leq k \leq 100$).
The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^5$).
Output
Print a single integer — the number of suitable pairs.
Example input
6 3 1 3 9 8 24 1
output
5
Note
In the sample case, the suitable pairs are:
- $a_1 \cdot a_4 = 8 = 2^3$;
- $a_1 \cdot a_6 = 1 = 1^3$;
- $a_2 \cdot a_3 = 27 = 3^3$;
- $a_3 \cdot a_5 = 216 = 6^3$;
- $a_4 \cdot a_6 = 8 = 2^3$.
Solution:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); const int MAX = 100010; vector<int> p(MAX); iota(p.begin(), p.end(), 0); for (int i = 2; i < MAX; i++) { if (p[i] == i) { for (int j = i + i; j < MAX; j += i) { if (p[j] == j) { p[j] = i; } } } } int n, k; cin >> n >> k; vector<int> cnt(MAX); long long ans = 0; for (int i = 0; i < n; i++) { int x; cin >> x; int res = 1; long long ask = 1; while (x > 1) { int y = p[x]; int cc = 0; while (x % y == 0) { x /= y; ++cc; } cc %= k; for (int j = 0; j < cc; j++) { res *= y; } for (int j = 0; j < (k - cc) % k; j++) { ask *= y; ask = min(ask, MAX - 1LL); } } ans += cnt[ask]; ++cnt[res]; } cout << ans << '\n'; return 0; }
Related posts:
Maximums
Tài liệu giáo khoa chuyên Tin 3 quyển
New Year and Ascent Sequence
Tree Factory
Intellectual Inquiry
The Art of Dealing with ATM
Happy Cactus
Flawed Flow
Banners
Rowena Ravenclaw's Diadem
Captains Mode
Board Game
New Year and Hurry
One-Based Arithmetic
Watchmen
Dice Tower
Inversions problem
Dima and Game
Parallel Programming
Closest Equals
D´Esopo-Pape algorithm
Aho-Corasick algorithm
Circle-Line Intersection
Dice Tower
Yet Another Array Queries Problem
Alternating Current
Tennis Rackets
Wonder Room
Uniqueness
Optimal schedule of jobs given their deadlines and durations
Encoding
Dima and Figure