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

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;
}  

结果:

6

时间复杂度: O(n ^ 2),使用嵌套循环

辅助空间: O(1),不使用额外空间

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例