Count of pairs from first N natural numbers with remainder at least K | C ++ program for the above approach ; Function to count the number of pairs ( a , b ) such that a % b is at least K ; Base Case ; Stores resultant count of pairs ; Iterate over the range [ K + 1 , N ] ; Find the cycled elements ; Find the remaining elements ; Return the resultant possible count of pairs ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countTotalPairs ( int N , int K ) { if ( K == 0 ) { return N * N ; } int ans = 0 ; for ( int b = K + 1 ; b <= N ; b ++ ) { ans += ( N / b ) * ( b - K ) ; ans += max ( N % b - K + 1 , 0 ) ; } return ans ; } int main ( ) { int N = 5 , K = 2 ; cout << countTotalPairs ( N , K ) ; return 0 ; }