C++程序找到一个数的幂乘积等于另一个数

给定一个长度为 n 的数组 A[] 和一个正整数 k（k > 1），现在您需要找到数量为 Ai，Aj 的数对，使得： **Ai = Aj*(k x ) ** 其中x是整数。

注意：（Ai，Aj）和（Aj，Ai）必须计数一次。

例：

输入：A[] = {3, 6, 4, 2}，k = 2
输出：2
解释：我们只有两个数对（4、2）和（3、6）

输入：A[] = {2，2，2} ，k = 2
输出：3
解释：（2，2），（2，2），（2，2）
即（A1，A2），（A2，A3）和（A1，A3）是共三个总数的数对，其中Ai = Aj *（k ^ 0）

要解决这个问题，我们首先对给定的数组进行排序，然后对于每个元素Ai，我们找到等于值Ai*k^x的元素数，不同的x的值，直到Ai*k^x小于等于Ai中最大的值。

算法：

    // sort the given array
    sort(A, A+n);

    // for each A[i] traverse rest array
    for (i = 0 to n-1)
    {
        for (j = i+1 to n-1)
        {
            // count Aj such that Ai*k^x = Aj
            int x = 0;

            // increase x till Ai * k^x lesser than 
            // largest element
            while ((A[i]*pow(k, x)) ≤ A[j])
            {
                if ((A[i]*pow(k, x)) == A[j])
                {              
                     ans++;
                     break;
                }
                x++;
            }        
        }   
    }
    // return answer
    return ans;

// Program to find pairs count
#include <bits/stdc++.h>
using namespace std;
 
// function to count the required pairs
int countPairs(int A[], int n, int k) {
  int ans = 0;
  // sort the given array
  sort(A, A + n);
 
  // for each A[i] traverse rest array
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
 
      // count Aj such that Ai*k^x = Aj
      int x = 0;
 
      // increase x till Ai * k^x <= largest element
      while ((A[i] * pow(k, x)) <= A[j]) {
        if ((A[i] * pow(k, x)) == A[j]) {
          ans++;
          break;
        }
        x++;
      }
    }
  }
  return ans;
}
 
// driver program
int main() {
  int A[] = {3, 8, 9, 12, 18, 4, 24, 2, 6};
  int n = sizeof(A) / sizeof(A[0]);
  int k = 3;
  cout << countPairs(A, n, k);
  return 0;
}

结果：

时间复杂度： O（n ^ 2），使用嵌套循环

辅助空间： O（1），不使用额外空间