Contar todos los pares de divisores de un número N cuya suma es coprima con N

Dado un número entero N , la tarea es contar todos los pares de divisores de N tales que la suma de cada par sea coprima con N .
Ejemplos: 
 

Entrada: N = 24 
Salida: 2 
Explicación: 
Hay 2 pares (1, 24) y (2, 3) cuya suma es coprima con 24
Entrada: 105 
Salida: 4 
Explicación: 
Hay 4 pares (1, 105), ( 3, 35), (5, 21) y (7, 15) cuya suma es coprima con 105 
 

Enfoque:
para resolver el problema mencionado anteriormente, podemos calcular fácilmente el resultado encontrando todos los divisores en √N de complejidad y verificar para cada par, si su suma es coprima con N o no.
A continuación se muestra la implementación del enfoque anterior:
 

// 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 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 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# 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));
    }
}

<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

Complejidad de tiempo: O(√N * log(N))