Given an integer N, the task is to count all pairs of divisors of N such that the sum of each pair is coprime with N.
Examples:
Input: N = 24
Output: 2
Explanation:
There are 2 pairs (1, 24) and (2, 3) whose sum is coprime with 24Input: 105
Output: 4
Explanation:
There are 4 pairs (1, 105), (3, 35), (5, 21) and (7, 15) whose sum is coprime with 105
Approach:
To solve the problem mentioned above we can easily calculate the result by finding all divisors in ?N complexity, and check for each pair, whether its sum is coprime with N or not.’
Below is the implementation of the above approach:
C++
// C++ program to count all pairs // of divisors such that their sum // is coprime with N #include <bits/stdc++.h> using namespace std; // Function to calculate GCD int gcd( int a, int b) { if (b == 0) return a; return (gcd(b, a % b)); } // Function to count all valid pairs int CountPairs( int n) { // Initialize count int cnt = 0; for ( int i = 1; i * i <= n; i++) { if (n % i == 0) { int div1 = i; int div2 = n / i; int sum = div1 + div2; // Check if sum of pair // and n are coprime if (gcd(sum, n) == 1) cnt += 1; } } // Return the result return cnt; } // Driver code int main() { int n = 24; cout << CountPairs(n) << endl; return 0; } |
Java
// Java program to count all pairs // of divisors such that their sum // is coprime with N import java.util.*; class GFG{ // Function to calculate GCD public static int gcd( int a, int b) { if (b == 0 ) return a; return (gcd(b, a % b)); } // Function to count all valid pairs public static int CountPairs( int n) { // Initialize count int cnt = 0 ; for ( int i = 1 ; i * i <= n; i++) { if (n % i == 0 ) { int div1 = i; int div2 = n / i; int sum = div1 + div2; // Check if sum of pair // and n are coprime if (gcd(sum, n) == 1 ) cnt += 1 ; } } // Return the result return cnt; } // Driver code public static void main(String[] args) { int n = 24 ; System.out.println(CountPairs(n)); } } // This code is contributed by equbalzeeshan |
Python3
# Python3 program to count all pairs # of divisors such that their sum # is coprime with N import math as m # Function to count all valid pairs def CountPairs(n): # initialize count cnt = 0 i = 1 while i * i < = n : if (n % i = = 0 ): div1 = i div2 = n / / i sum = div1 + div2; # Check if sum of pair # and n are coprime if ( m.gcd( sum , n) = = 1 ): cnt + = 1 i + = 1 # Return the result return cnt # Driver code n = 24 print (CountPairs(n)) |
C#
// C# program to count all pairs of // divisors such that their sum // is coprime with N using System; class GFG { // Function to find gcd of a and b static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count all valid pairs static int CountPairs( int n) { // Initialize count int cnt = 0; for ( int i = 1; i * i <= n; i++) { if (n % i == 0) { int div1 = i; int div2 = n / i; int sum = div1 + div2; // Check if sum of pair // and n are coprime if (gcd(sum, n) == 1) cnt += 1; } } // Return the result return cnt; } // Driver method public static void Main() { int n = 24; Console.WriteLine(CountPairs(n)); } } |
Javascript
<script> // JavaScript program to count all pairs // of divisors such that their sum // is coprime with N // Function to calculate GCD function gcd(a, b) { if (b == 0) return a; return (gcd(b, a % b)); } // Function to count all valid pairs function CountPairs(n) { // Initialize count let cnt = 0; for (let i = 1; i * i <= n; i++) { if (n % i == 0) { let div1 = i; let div2 = Math.floor(n / i); let sum = div1 + div2; // Check if sum of pair // and n are coprime if (gcd(sum, n) == 1) cnt += 1; } } // Return the result return cnt; } // Driver code let n = 24; document.write(CountPairs(n) + "<br>" ); // This code is contributed by Surbhi Tyagi. </script> |
2
Time Complexity: O(?N * log(N))
Auxiliary Space: O(log(min(a,b)) for call stack
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!