Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B
Given a number n. We need to find the number of ordered pairs of a and b such gcd(a, b) is b itself
Examples :
Input : n = 2 Output : 3 (1, 1) (2, 2) and (2, 1) Input : n = 3 Output : 5 (1, 1) (2, 2) (3, 3) (2, 1) and (3, 1)
Naive approach: gcd(a, b) = b means b is a factor of a. So the total number of pairs will be equal to sum of divisors for each a = 1 to n. Please refer find all divisors of a natural number for implementation.
Efficient approach: gcd(a, b) = b means that a is a multiple of b. So the total number of pairs will be sum of number of multiples of each b (where b varies from 1 to n) which are less than or equal to n.
For a number i, a number of multiples of i is less than or equal to floor(n/i). So what we need to do is just sum the floor(n/i) for each i = 1 to n and print it. But more optimizations can be done. floor(n/i) can have atmost 2*sqrt(n) values for i >= sqrt(n). floor(n/i) can vary from 1 to sqrt(n) and similarly for i = 1 to sqrt(n) floor(n/i) can have values from 1 to sqrt(n). So total of 2*sqrt(n) distinct values
let floor(n/i) = k k <= n/i < k + 1 n/k+1 < i <= n/k floor(n/k+1) < i <= floor(n/k) Thus for given k the largest value of i for which the floor(n/i) = k is floor(n/k) and all the set of i for which the floor(n/i) = k are consecutive
CPP
// C++ implementation of counting pairs // such that gcd (a, b) = b #include <bits/stdc++.h> using namespace std; // returns number of valid pairs int CountPairs( int n) { // initialize k int k = n; // loop till imin <= n int imin = 1; // Initialize result int ans = 0; while (imin <= n) { // max i with given k floor(n/k) int imax = n / k; // adding k*(number of i with // floor(n/i) = k to ans ans += k * (imax - imin + 1); // set imin = imax + 1 and k = n/imin imin = imax + 1; k = n / imin; } return ans; } // Driver function int main() { cout << CountPairs(1) << endl; cout << CountPairs(2) << endl; cout << CountPairs(3) << endl; return 0; } |
Java
// Java implementation of counting pairs // such that gcd (a, b) = b import java.io.*; public class GFG { // returns number of valid pairs static int CountPairs( int n) { // initialize k int k = n; // loop till imin <= n int imin = 1 ; // Initialize result int ans = 0 ; while (imin <= n) { // max i with given k floor(n/k) int imax = n / k; // adding k*(number of i with // floor(n/i) = k to ans ans += k * (imax - imin + 1 ); // set imin = imax + 1 // and k = n/imin imin = imax + 1 ; k = n / imin; } return ans; } // Driver code public static void main(String[] args) { System.out.println(CountPairs( 1 )); System.out.println(CountPairs( 2 )); System.out.println(CountPairs( 3 )); } } // This code is contributed by Anant Agarwal. |
Python3
# Python implementation of counting # pairs such that gcd (a, b) = b # returns number of valid pairs def CountPairs(n): # initialize k k = n # loop till imin <= n imin = 1 # Initialize result ans = 0 while (imin < = n): # max i with given k floor(n / k) imax = n / k # adding k*(number of i with # floor(n / i) = k to ans ans + = k * (imax - imin + 1 ) # set imin = imax + 1 and # k = n / imin imin = imax + 1 k = n / imin return ans # Driver code print (CountPairs( 1 )) print (CountPairs( 2 )) print (CountPairs( 3 )) # This code is contributed by Anant Agarwal. |
C#
// C# implementation of counting // pairs such that gcd (a, b) = b using System; class GFG { // returns number of valid pairs static int CountPairs( int n) { // initialize k int k = n; // loop till imin <= n int imin = 1; // Initialize result int ans = 0; while (imin <= n) { // max i with given // k floor(n / k) int imax = n / k; // adding k * (number of i // with floor(n / i) = k // to ans ans += k * (imax - imin + 1); // set imin = imax + 1 // and k = n / imin imin = imax + 1; k = n / imin; } return ans; } // Driver code public static void Main(String []args) { Console.WriteLine(CountPairs(1)); Console.WriteLine(CountPairs(2)); Console.WriteLine(CountPairs(3)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP implementation of counting // pairs such that gcd (a, b) = b // returns number of valid pairs function CountPairs( $n ) { // initialize k $k = $n ; // loop till imin <= n $imin = 1; // Initialize result $ans = 0; while ( $imin <= $n ) { // max i with given k floor(n/k) $imax = $n / $k ; // adding k*(number of i with // floor(n/i) = k to ans $ans += $k * ( $imax - $imin + 1); // set imin = imax + 1 // and k = n/imin $imin = $imax + 1; $k = (int)( $n / $imin ); } return $ans ; } // Driver Code echo (CountPairs(1) . "\n" ); echo (CountPairs(2) . "\n" ); echo (CountPairs(3) . "\n" ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript implementation of counting pairs // such that gcd (a, b) = b // returns number of valid pairs function CountPairs(n) { // initialize k let k = n; // loop till imin <= n let imin = 1; // Initialize result let ans = 0; while (imin <= n) { // max i with given k floor(n/k) let imax = Math.floor(n / k); // adding k*(number of i with // floor(n/i) = k to ans ans += k * (imax - imin + 1); // set imin = imax + 1 and k = n/imin imin = imax + 1; k = Math.floor(n / imin); } return ans; } // Driver function document.write(CountPairs(1) + "<br>" ); document.write(CountPairs(2) + "<br>" ); document.write(CountPairs(3) + "<br>" ); // This is code is contributed by Mayank Tyagi </script> |
1 3 5
Time complexity: O(n). This is because the while loop takes O(n) time to complete since it is looping over all elements of the array.
Auxiliary space: O(1), as no extra space is used.
Contact Us