给你一个由n个元素组成的数组A[]和一个正整数k。现在你已经找到了成对数Ai，Aj，这样 Ai=Aj*（k） 十、 ) 其中x是一个整数。 注：（Ai，Aj）和（Aj，Ai）必须计数一次。 例如：
null
Input : A[] = {3, 6, 4, 2}, k = 2Output : 2Explanation : We have only two pairs (4, 2) and (3, 6)Input : A[] = {2, 2, 2}, k = 2Output : 3Explanation : (2, 2), (2, 2), (2, 2) that are (A1, A2), (A2, A3) and (A1, A3) are total three pairs where Ai = Aj * (k^0)
为了解决这个问题，我们首先对给定的数组进行排序，然后对于每个元素Ai，我们发现对于不同的x值，元素数等于Ai*k^x，直到Ai*k^x小于或等于Ai的最大值。 算法：
// 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 answer return ans;
C++
// 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; } |
JAVA
// Java program to find pairs count import java.io.*; import java .util.*; class GFG { // function to count the required pairs static int countPairs( int A[], int n, int k) { int ans = 0 ; // sort the given array Arrays.sort(A); // 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] * Math.pow(k, x)) <= A[j]) { if ((A[i] * Math.pow(k, x)) == A[j]) { ans++; break ; } x++; } } } return ans; } // Driver program public static void main (String[] args) { int A[] = { 3 , 8 , 9 , 12 , 18 , 4 , 24 , 2 , 6 }; int n = A.length; int k = 3 ; System.out.println (countPairs(A, n, k)); } } // This code is contributed by vt_m. |
Python3
# Program to find pairs count import math # function to count the required pairs def countPairs(A, n, k): ans = 0 # sort the given array A.sort() # for each A[i] traverse rest array for i in range ( 0 ,n): for j in range (i + 1 , n): # count Aj such that Ai*k^x = Aj x = 0 # increase x till Ai * k^x <= largest element while ((A[i] * math. pow (k, x)) < = A[j]) : if ((A[i] * math. pow (k, x)) = = A[j]) : ans + = 1 break x + = 1 return ans # driver program A = [ 3 , 8 , 9 , 12 , 18 , 4 , 24 , 2 , 6 ] n = len (A) k = 3 print (countPairs(A, n, k)) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# program to find pairs count using System; class GFG { // function to count the required pairs static int countPairs( int []A, int n, int k) { int ans = 0; // sort the given array Array.Sort(A); // 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] * Math.Pow(k, x)) <= A[j]) { if ((A[i] * Math.Pow(k, x)) == A[j]) { ans++; break ; } x++; } } } return ans; } // Driver program public static void Main () { int []A = {3, 8, 9, 12, 18, 4, 24, 2, 6}; int n = A.Length; int k = 3; Console.WriteLine(countPairs(A, n, k)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Program to find pairs count // function to count // the required pairs function countPairs( $A , $n , $k ) { $ans = 0; // sort the given array sort( $A ); // for each A[i] // traverse rest array for ( $i = 0; $i < $n ; $i ++) { for ( $j = $i + 1; $j < $n ; $j ++) { // count Aj such that Ai*k^x = Aj $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 Code $A = array (3, 8, 9, 12, 18, 4, 24, 2, 6); $n = count ( $A ); $k = 3; echo countPairs( $A , $n , $k ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript Program to find pairs count // function to count the required pairs function countPairs(A, n, k) { var ans = 0; // sort the given array A.sort((a,b)=>a-b) // for each A[i] traverse rest array for ( var i = 0; i < n; i++) { for ( var j = i + 1; j < n; j++) { // count Aj such that Ai*k^x = Aj var x = 0; // increase x till Ai * k^x <= largest element while ((A[i] * Math.pow(k, x)) <= A[j]) { if ((A[i] * Math.pow(k, x)) == A[j]) { ans++; break ; } x++; } } } return ans; } // driver program var A = [3, 8, 9, 12, 18, 4, 24, 2, 6]; var n = A.length; var k = 3; document.write( countPairs(A, n, k)); // This code is contributed by rutvik_56. </script> |
输出：
6
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
