El primer N natural se puede dividir en dos conjuntos con diferencia dada y sumas coprimas

Dados N y M, la tarea es encontrar si los números 1 a N se pueden dividir en dos conjuntos de manera que la diferencia absoluta entre la suma de dos conjuntos sea M y el gcd de la suma de dos conjuntos sea 1 (es decir, la suma de ambos conjuntos es co-prime). 
Requisito previo: GCD en CPP | Ejemplos de GCD :

 

Entrada: N = 5 y M = 7 
Salida: SI 
Explicación: como los números del 1 al 5 se pueden dividir en dos conjuntos {1, 2, 3, 5} y {4} tal que la diferencia absoluta entre la suma de ambos conjuntos es 11 – 4 = 7 que es igual a M y también MCD(11, 4) = 1.
Entrada: N = 6 y M = 3 
Salida: NO 
Explicación: En este caso, los números del 1 al 6 se pueden dividir en dos conjuntos {1, 2, 4, 5} y {3, 6} tales que la diferencia absoluta entre su suma es 12 – 9 = 3. Pero, dado que 12 y 9 no son coprimos como MCD(12, 9) = 3, la respuesta es no’.

Enfoque: Como tenemos de 1 a N números, sabemos que la suma de todos los números es N * (N + 1) / 2. Sean S1 y S2 dos conjuntos tales que, 
1) sum(S1) + sum(S2 ) = N * (N + 1) / 2 
2) sum(S1) – sum(S2) = M 
Resolver estas dos ecuaciones nos dará la suma de ambos conjuntos. Si sum(S1) y sum(S2) son enteros y son coprimos (su MCD es 1), entonces existe una forma de dividir los números en dos conjuntos. De lo contrario, no hay forma de dividir estos N números.
A continuación se muestra la implementación de la solución descrita anteriormente. 
 

/* CPP code to determine whether numbers
   1 to N can be divided into two sets
   such that absolute difference between
   sum of these two sets is M and these
   two sum are co-prime*/
#include <bits/stdc++.h>
using namespace std;
 
// function that returns boolean value
// on the basis of whether it is possible
// to divide 1 to N numbers into two sets
// that satisfy given conditions.
bool isSplittable(int n, int m)
{
    // initializing total sum of 1
    // to n numbers
    int total_sum = (n * (n + 1)) / 2;
 
    // since (1) total_sum = sum_s1 + sum_s2
    // and (2) m = sum_s1 - sum_s2
    // assuming sum_s1 > sum_s2.
    // solving these 2 equations to get
    // sum_s1 and sum_s2
    int sum_s1 = (total_sum + m) / 2;
 
    // total_sum = sum_s1 + sum_s2
    // and therefore
    int sum_s2 = total_sum - sum_s1;
 
    // if total sum is less than the absolute
    // difference then there is no way we
    // can split n numbers into two sets
    // so return false
    if (total_sum < m)
        return false;
 
    // check if these two sums are
    // integers and they add up to
    // total sum and also if their
    // absolute difference is m.
    if (sum_s1 + sum_s2 == total_sum &&
        sum_s1 - sum_s2 == m)
 
        // Now if two sum are co-prime
        // then return true, else return false.
        return (__gcd(sum_s1, sum_s2) == 1);
 
    // if two sums don't add up to total
    // sum or if their absolute difference
    // is not m, then there is no way to
    // split n numbers, hence return false
    return false;
}
 
// Driver code
int main()
{
    int n = 5, m = 7;
 
    // function call to determine answer
    if (isSplittable(n, m))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

/* Java code to determine whether numbers
1 to N can be divided into two sets
such that absolute difference between
sum of these two sets is M and these
two sum are co-prime*/
class GFG
{
    static int GCD (int a, int b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }
     
    // function that returns boolean value
    // on the basis of whether it is possible
    // to divide 1 to N numbers into two sets
    // that satisfy given conditions.
    static boolean isSplittable(int n, int m)
    {
         
        // initializing total sum of 1
        // to n numbers
        int total_sum = (n * (n + 1)) / 2;
     
        // since (1) total_sum = sum_s1 + sum_s2
        // and (2) m = sum_s1 - sum_s2
        // assuming sum_s1 > sum_s2.
        // solving these 2 equations to get
        // sum_s1 and sum_s2
        int sum_s1 = (total_sum + m) / 2;
     
        // total_sum = sum_s1 + sum_s2
        // and therefore
        int sum_s2 = total_sum - sum_s1;
     
        // if total sum is less than the absolute
        // difference then there is no way we
        // can split n numbers into two sets
        // so return false
        if (total_sum < m)
            return false;
     
        // check if these two sums are
        // integers and they add up to
        // total sum and also if their
        // absolute difference is m.
        if (sum_s1 + sum_s2 == total_sum &&
                    sum_s1 - sum_s2 == m)
     
            // Now if two sum are co-prime
            // then return true, else return false.
            return (GCD(sum_s1, sum_s2) == 1);
 
        // if two sums don't add up to total
        // sum or if their absolute difference
        // is not m, then there is no way to
        // split n numbers, hence return false
        return false;
    }
     
    // Driver Code
    public static void main(String args[])
    {
        int n = 5, m = 7;
 
        // function call to determine answer
        if (isSplittable(n, m))
            System.out.println("Yes");
        else
            System.out.println("No");
         
    }
}
 
// This code is contributed by Sam007

# Python3 code to determine whether numbers
# 1 to N can be divided into two sets
# such that absolute difference between
# sum of these two sets is M and these
# two sum are co-prime
 
def __gcd (a, b):
 
        return a if(b == 0) else __gcd(b, a % b);
 
# function that returns boolean value
# on the basis of whether it is possible
# to divide 1 to N numbers into two sets
# that satisfy given conditions.
def isSplittable(n, m):
 
    # initializing total sum of 1
    # to n numbers
    total_sum = (int)((n * (n + 1)) / 2);
 
    # since (1) total_sum = sum_s1 + sum_s2
    # and (2) m = sum_s1 - sum_s2
    # assuming sum_s1 > sum_s2.
    # solving these 2 equations to get
    # sum_s1 and sum_s2
    sum_s1 = int((total_sum + m) / 2);
 
    # total_sum = sum_s1 + sum_s2
    # and therefore
    sum_s2 = total_sum - sum_s1;
 
    # if total sum is less than the absolute
    # difference then there is no way we
    # can split n numbers into two sets
    # so return false
    if (total_sum < m):
        return False;
 
    # check if these two sums are
    # integers and they add up to
    # total sum and also if their
    # absolute difference is m.
    if (sum_s1 + sum_s2 == total_sum and
                 sum_s1 - sum_s2 == m):
 
        # Now if two sum are co-prime
        # then return true, else return false.
        return (__gcd(sum_s1, sum_s2) == 1);
 
    # if two sums don't add up to total
    # sum or if their absolute difference
    # is not m, then there is no way to
    # split n numbers, hence return false
    return False;
 
# Driver code
n = 5;
m = 7;
 
# function call to determine answer
if (isSplittable(n, m)):
    print("Yes");
else:
    print("No");
 
# This code is contributed by mits

/* C# code to determine whether numbers
1 to N can be divided into two sets
such that absolute difference between
sum of these two sets is M and these
two sum are co-prime*/
using System;
 
class GFG {
 
    static int GCD (int a, int b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }
     
    // function that returns boolean value
    // on the basis of whether it is possible
    // to divide 1 to N numbers into two sets
    // that satisfy given conditions.
    static bool isSplittable(int n, int m)
    {
         
        // initializing total sum of 1
        // to n numbers
        int total_sum = (n * (n + 1)) / 2;
     
        // since (1) total_sum = sum_s1 + sum_s2
        // and (2) m = sum_s1 - sum_s2
        // assuming sum_s1 > sum_s2.
        // solving these 2 equations to get
        // sum_s1 and sum_s2
        int sum_s1 = (total_sum + m) / 2;
     
        // total_sum = sum_s1 + sum_s2
        // and therefore
        int sum_s2 = total_sum - sum_s1;
     
        // if total sum is less than the absolute
        // difference then there is no way we
        // can split n numbers into two sets
        // so return false
        if (total_sum < m)
            return false;
     
        // check if these two sums are
        // integers and they add up to
        // total sum and also if their
        // absolute difference is m.
        if (sum_s1 + sum_s2 == total_sum &&
                       sum_s1 - sum_s2 == m)
     
            // Now if two sum are co-prime
            // then return true, else return false.
            return (GCD(sum_s1, sum_s2) == 1);
 
        // if two sums don't add up to total
        // sum or if their absolute difference
        // is not m, then there is no way to
        // split n numbers, hence return false
        return false;
    }
     
    // Driver code
    public static void Main()
    {
        int n = 5, m = 7;
 
        // function call to determine answer
        if (isSplittable(n, m))
            Console.Write("Yes");
        else
            Console.Write("No");
    }
}
 
// This code is contributed by Sam007.

<?php
/* PHP code to determine whether numbers
1 to N can be divided into two sets
such that absolute difference between
sum of these two sets is M and these
two sum are co-prime*/
 
function __gcd ($a, $b)
{
        return $b == 0 ? $a : __gcd($b, $a % $b);
}
 
// function that returns boolean value
// on the basis of whether it is possible
// to divide 1 to N numbers into two sets
// that satisfy given conditions.
function isSplittable($n, $m)
{
    // initializing total sum of 1
    // to n numbers
    $total_sum = (int)(($n * ($n + 1)) / 2);
 
    // since (1) total_sum = sum_s1 + sum_s2
    // and (2) m = sum_s1 - sum_s2
    // assuming sum_s1 > sum_s2.
    // solving these 2 equations to get
    // sum_s1 and sum_s2
    $sum_s1 = (int)(($total_sum + $m) / 2);
 
    // total_sum = sum_s1 + sum_s2
    // and therefore
    $sum_s2 = $total_sum - $sum_s1;
 
    // if total sum is less than the absolute
    // difference then there is no way we
    // can split n numbers into two sets
    // so return false
    if ($total_sum < $m)
        return false;
 
    // check if these two sums are
    // integers and they add up to
    // total sum and also if their
    // absolute difference is m.
    if ($sum_s1 + $sum_s2 == $total_sum &&
        $sum_s1 - $sum_s2 == $m)
 
        // Now if two sum are co-prime
        // then return true, else return false.
        return (__gcd($sum_s1, $sum_s2) == 1);
 
    // if two sums don't add up to total
    // sum or if their absolute difference
    // is not m, then there is no way to
    // split n numbers, hence return false
    return false;
}
 
// Driver code
$n = 5;
$m = 7;
 
// function call to determine answer
if (isSplittable($n, $m))
    echo "Yes";
else
    echo "No";
 
// This Code is Contributed by mits
?>

<script>
 
/* Javascript code to determine whether numbers
1 to N can be divided into two sets
such that absolute difference between
sum of these two sets is M and these
two sum are co-prime*/
 
function __gcd (a, b)
{
        return b == 0 ? a : __gcd(b, a % b);
}
 
// function that returns boolean value
// on the basis of whether it is possible
// to divide 1 to N numbers into two sets
// that satisfy given conditions.
function isSplittable(n, m)
{
    // initializing total sum of 1
    // to n numbers
    let total_sum = parseInt((n * (n + 1)) / 2);
 
    // since (1) total_sum = sum_s1 + sum_s2
    // and (2) m = sum_s1 - sum_s2
    // assuming sum_s1 > sum_s2.
    // solving these 2 equations to get
    // sum_s1 and sum_s2
    let sum_s1 = parseInt((total_sum + m) / 2);
 
    // total_sum = sum_s1 + sum_s2
    // and therefore
    let sum_s2 = total_sum - sum_s1;
 
    // if total sum is less than the absolute
    // difference then there is no way we
    // can split n numbers into two sets
    // so return false
    if (total_sum < m)
        return false;
 
    // check if these two sums are
    // integers and they add up to
    // total sum and also if their
    // absolute difference is m.
    if (sum_s1 + sum_s2 == total_sum &&
        sum_s1 - sum_s2 == m)
 
        // Now if two sum are co-prime
        // then return true, else return false.
        return (__gcd(sum_s1, sum_s2) == 1);
 
    // if two sums don't add up to total
    // sum or if their absolute difference
    // is not m, then there is no way to
    // split n numbers, hence return false
    return false;
}
 
// Driver code
let n = 5;
let m = 7;
 
// function call to determine answer
if (isSplittable(n, m))
    document.write("Yes");
else
    document.write("No");
 
// This Code is Contributed by _saurabh_jaiswal
 
</script>

Yes

Complejidad de tiempo: O(log(n))
Espacio auxiliar: O(1)

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.