Number of Co | C ++ program to count the pairs whose sum of digits is co - prime ; Recursive function to return the frequency of numbers having their sum of digits i ; Returns 1 or 0 ; Returns value of the dp if already stored ; Loop from digit 0 to 9 ; To change the tight to 1 ; Calling the recursive function to find the frequency ; Function to find out frequency of numbers from 1 to N having their sum of digits from 1 to 162 and store them in array ; Number to string conversion ; Calling the recursive function and pushing it into array ; Function to find the pairs ; Calling the formArray function of a - 1 numbers ; Calling the formArray function of b numbers ; Subtracting the frequency of higher number array with lower number array and thus finding the range of numbers from a to b having sum from 1 to 162 ; To find out total number of pairs which are co - prime ; Driver code ; Function to count the pairs
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE using namespace std ; ll recursive ( ll idx , ll sum , ll tight , string st , ll dp [ 20 ] [ 2 ] [ 166 ] , ll num ) { if ( idx == num ) return sum == 0 ; if ( dp [ idx ] [ tight ] [ sum ] != -1 ) return dp [ idx ] [ tight ] [ sum ] ; bool newTight ; ll ans = 0 ; ll d ; for ( d = 0 ; d < 10 ; ++ d ) { newTight = false ; if ( tight && st [ idx ] - '0' < d ) continue ; if ( tight && st [ idx ] - '0' == d ) newTight = true ; if ( sum >= d ) ans += recursive ( idx + 1 , sum - d , newTight , st , dp , num ) ; } return dp [ idx ] [ tight ] [ sum ] = ans ; } vector < ll > formArray ( ll N ) { ll dp [ 20 ] [ 2 ] [ 166 ] ; memset ( dp , -1 , sizeof dp ) ; ostringstream x ; x << N ; string st = x . str ( ) ; ll num = st . size ( ) ; vector < ll > arr ; for ( int i = 1 ; i <= 162 ; ++ i ) { arr . push_back ( recursive ( 0 , i , 1 , st , dp , num ) ) ; } return arr ; } ll findPair ( ll a , ll b ) { vector < ll > arr_smaller = formArray ( a - 1 ) ; vector < ll > arr_greater = formArray ( b ) ; for ( int i = 0 ; i < arr_greater . size ( ) ; ++ i ) arr_greater [ i ] -= arr_smaller [ i ] ; int ans = 0 ; for ( int i = 1 ; i <= 162 ; ++ i ) { for ( int j = i + 1 ; j <= 162 ; ++ j ) { if ( __gcd ( i , j ) == 1 ) ans = ( ans + arr_greater [ i - 1 ] * arr_greater [ j - 1 ] ) ; } } return ans ; } int main ( ) { ll a = 12 , b = 15 ; cout << findPair ( a , b ) ; return 0 ; }