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:
Maximum flow - Push-relabel method improved
K Integers
Gena and Second Distance
Extended Euclidean Algorithm
Constrained Tree
Cow and Haybales
Sereja and the Arrangement of Numbers
Cowboy Beblop at his computer
Eevee
Cow and Exercise
Watchmen
Divide Points
Party
Stairs and Elevators
Magic Trick
TorCoder
Photo to Remember
Kuroni and the Celebration
Finding the largest zero submatrix
Length of the union of segments
Niyaz and Small Degrees
NP-Hard Problem
Desk Disorder
New Year and Old Property
New Year Shopping
Bathroom terminal
New Year and Permutation
Potions Homework
New Year Permutation
To Play or not to Play
Borya and Hanabi
Discrete Root