text: Count ways to represent an integer as an exponent | C ++ program for the above approach ; Function to calculate GCD of a and b using Euclidean Algorithm ; Iterate until b is non - zero ; Return the GCD ; Function to count the number of ways N can be expressed as x ^ y ; Base Case ; Stores the gcd of powers ; Calculate the degree of 2 in N ; Calculate the degree of prime numbers in N ; Calculate the degree of prime ' i ' in N ; If N is a prime , g becomes 1. ; Stores the number of ways to represent N as x ^ y ; Find the number of Factors of g ; Update the count of ways ; Iterate to find rest of the prime numbers ; Find the power of i ; Update the count of ways ; If g is prime ; Return the total number of ways ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; long long int gcd ( long long int a , long long int b ) { while ( b > 0 ) { long long int rem = a % b ; a = b ; b = rem ; } return a ; } int countNumberOfWays ( long long int n ) { if ( n == 1 ) return -1 ; long long int g = 0 ; int power = 0 ; while ( n % 2 == 0 ) { power ++ ; n /= 2 ; } g = gcd ( g , power ) ; for ( int i = 3 ; i <= sqrt ( n ) ; i += 2 ) { power = 0 ; while ( n % i == 0 ) { power ++ ; n /= i ; } g = gcd ( g , power ) ; } if ( n > 2 ) g = gcd ( g , 1 ) ; int ways = 1 ; power = 0 ; while ( g % 2 == 0 ) { g /= 2 ; power ++ ; } ways *= ( power + 1 ) ; for ( int i = 3 ; i <= sqrt ( g ) ; i += 2 ) { power = 0 ; while ( g % i == 0 ) { power ++ ; g /= i ; } ways *= ( power + 1 ) ; } if ( g > 2 ) ways *= 2 ; return ways ; } int main ( ) { int N = 64 ; cout << countNumberOfWays ( N ) ; return 0 ; }