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:
Special Task
Largest Submatrix 3
Dynamic Programming on Broken Profile
Little Artem and Random Variable
Walk on Matrix
Chicken or Fish?
Graph Decomposition
Ordering Pizza
Prüfer code
Table Compression
New Year Tree Decorations
Nikita and stack
Train Hard, Win Easy
Bear and Blocks
New Year and Cleaning
Party
New Year Book Reading
Fox And Jumping
Hongcow's Game
Double Elimination
King of Thieves
Antipalindrome
Rectangle Puzzle
Giáo trình Thuật toán - Ngọc Anh Thư
Three Blocks Palindrome
New Year and Ascent Sequence
Check if two segments intersect
Looksery Party
Degenerate Matrix
Hydra
Convex hull trick and Li Chao tree
New Year and Permutation