Count number of pairs ( A <= N , B <= N ) such that gcd ( A , B ) is B | C ++ implementation of counting pairs such that gcd ( a , b ) = b ; returns number of valid pairs ; initialize k ; loop till imin <= n ; Initialize result ; max i with given k floor ( n / k ) ; adding k * ( number of i with floor ( n / i ) = k to ans ; set imin = imax + 1 and k = n / imin ; Driver function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int CountPairs ( int n ) { int k = n ; int imin = 1 ; int ans = 0 ; while ( imin <= n ) { int imax = n / k ; ans += k * ( imax - imin + 1 ) ; imin = imax + 1 ; k = n / imin ; } return ans ; } int main ( ) { cout << CountPairs ( 1 ) << endl ; cout << CountPairs ( 2 ) << endl ; cout << CountPairs ( 3 ) << endl ; return 0 ; }