Count number of pairs ( A <= N , B <= N ) such that gcd ( A , B ) is 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 Code
< ? php function CountPairs ( $ n ) { $ k = $ n ; $ imin = 1 ; $ ans = 0 ; while ( $ imin <= $ n ) { $ imax = $ n / $ k ; $ ans += $ k * ( $ imax - $ imin + 1 ) ; $ imin = $ imax + 1 ; $ k = ( int ) ( $ n / $ imin ) ; } return $ ans ; } echo ( CountPairs ( 1 ) . " STRNEWLINE " ) ; echo ( CountPairs ( 2 ) . " STRNEWLINE " ) ; echo ( CountPairs ( 3 ) . " STRNEWLINE " ) ; ? >