#include <bits/stdc++.h>   using namespace std;   const int maxn = int(1e6) + 100;   const long long inf = 1e6;   int n, m;   int a[maxn], cnt[maxn], b[maxn];   void read() {     scanf( %d%d , &n, &m);     for (int i = 1; i <= n; ++i) scanf( %d , &a[i]);     for (int i = 1; i <= n; ++i) b[i] = a[i];   }   long long POW(long long num, int times) {     long long ans = 1;     while (times) {       if (times & 1) ans = ans * num;       num = num * num;       if (ans >= inf) return inf;       if (num >= inf) num = inf;       times >>= 1;     }     return ans;   }   void solve() {     long long ans = 0;     for (int i = 1; i <= n; ++i) {       int num = a[i];       a[i] = 1;       long long inv = 1;       for (int j = 2; j * j <= num && num != 1; ++j)         if (num % j == 0) {           int k = 0;           int x = a[i];           while (num % j == 0) {             k++;             if (k == m) k = 0;             if (k == 0)               a[i] = x;             else               a[i] *= j;             num /= j;           }           int tmp = POW(j, (m - k) % m);           if (tmp == inf)             inv = inf;           else             inv *= tmp;           if (inv >= inf) inv = inf;         }       if (num != 1) a[i] *= num, inv *= POW(num, m - 1);       if (inv < inf) ans += cnt[inv];       ++cnt[a[i]];     }     printf( %lld n , ans);   }   int main() {     read();     solve();     return 0;   }   