Dado un entero n, imprima m números crecientes de manera que la suma de m números sea igual a n y el MCD de m números sea el máximo entre todas las series posibles. Si no es posible ninguna serie, imprima «-1».
Ejemplos:
Input : n = 24,
m = 3
Output : 4 8 12
Explanation : (3, 6, 15) is also a series
of m numbers which sums to N, but gcd = 3
(4, 8, 12) has gcd = 4 which is the maximum
possible.
Input : n = 6
m = 4
Output : -1
Explanation: It is not possible as the
least GCD sequence will be 1+2+3+4 which
is greater than n, hence print -1.
Enfoque:
La observación más común es que el mcd de la serie siempre será un divisor de n. El gcd máximo posible ( digamos b ) será n/suma, donde suma es la suma de 1+2+..m.
Si b resulta ser 0, entonces la suma de 1+2+3..+k excede n, lo cual no es válido, por lo tanto, genera «-1».
Traverse para encontrar todos los divisores posibles, un bucle hasta sqrt(n). Si el divisor actual es i, la mejor forma posible de tomar la serie será considerar i, 2*i, 3*i, …(m-1)*i, y su suma es s que es igual a i * ( m*(m-1))/2 . El último número será ns.
Además de ser i el divisor, n/i será el otro divisor, así que verifique eso también.
Tome el máximo de posible divisor posible ( digamos r) que debe ser menor o igual que b e imprimir la secuencia como r, 2*r, … (m-1)*r, n—s.
Si no se encuentran dichos divisores, simplemente emita «-1».
C++
// CPP program to find the series with largest
// GCD and sum equals to n
#include <bits/stdc++.h>
using namespace std;
// function to generate and print the sequence
void print_sequence(int n, int k)
{
// stores the maximum gcd that can be
// possible of sequence.
int b = n / (k * (k + 1) / 2);
// if maximum gcd comes out to be
// zero then not possible
if (b == 0) {
cout << -1 << endl;
} else {
// the smallest gcd possible is 1
int r = 1;
// traverse the array to find out
// the max gcd possible
for (int x = 1; x * x <= n; x++) {
// checks if the number is
// divisible or not
if (n % x != 0)
continue;
// checks if x is smaller than
// the max gcd possible and x
// is greater than the resultant
// gcd till now, then r=x
if (x <= b && x > r)
r = x;
// checks if n/x is smaller than
// the max gcd possible and n/x
// is greater than the resultant
// gcd till now, then r=x
if (n / x <= b && n / x > r)
r = n / x;
}
// traverses and prints d, 2d, 3d,
// ..., (k-1)·d,
for (int i = 1; i < k; i++)
cout << r * i << " ";
// computes the last element of
// the sequence n-s.
int res = n - (r * (k * (k - 1) / 2));
// prints the last element
cout << res << endl;
}
}
// driver program to test the above function
int main()
{
int n = 24;
int k = 4;
print_sequence(n, k);
n = 24, k = 5;
print_sequence(n, k);
n = 6, k = 4;
print_sequence(n, k);
}
Java
// Java program to find the series with
// largest GCD and sum equals to n
import java.io.*;
class GFG {
// function to generate and print the sequence
static void print_sequence(int n, int k)
{
// stores the maximum gcd that can be
// possible of sequence.
int b = n / (k * (k + 1) / 2);
// if maximum gcd comes out to be
// zero then not possible
if (b == 0) {
System.out.println("-1");
} else {
// the smallest gcd possible is 1
int r = 1;
// traverse the array to find out
// the max gcd possible
for (int x = 1; x * x <= n; x++) {
// checks if the number is
// divisible or not
if (n % x != 0)
continue;
// checks if x is smaller than
// the max gcd possible and x
// is greater than the resultant
// gcd till now, then r=x
if (x <= b && x > r)
r = x;
// checks if n/x is smaller than
// the max gcd possible and n/x
// is greater than the resultant
// gcd till now, then r=x
if (n / x <= b && n / x > r)
r = n / x;
}
// traverses and prints d, 2d, 3d,..., (k-1)
for (int i = 1; i < k; i++)
System.out.print(r * i + " ");
// computes the last element of
// the sequence n-s.
int res = n - (r * (k * (k - 1) / 2));
// prints the last element
System.out.println(res);
}
}
// driver program to test the above function
public static void main(String[] args)
{
int n = 24;
int k = 4;
print_sequence(n, k);
n = 24; k = 5;
print_sequence(n, k);
n = 6; k = 4;
print_sequence(n, k);
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 code to find the series
# with largest GCD and sum equals to n
def print_sequence(n, k):
# stores the maximum gcd that
# can be possible of sequence.
b = int(n / (k * (k + 1) / 2));
# if maximum gcd comes out to be
# zero then not possible
if b == 0:
print ("-1")
else:
# the smallest gcd possible is 1
r = 1;
# traverse the array to find out
# the max gcd possible
x = 1
while x ** 2 <= n:
# checks if the number is
# divisible or not
if n % x != 0:
# x = x + 1
continue;
# checks if x is smaller than
# the max gcd possible and x
# is greater than the resultant
# gcd till now, then r=x
elif x <= b and x > r:
r = x
# x = x + 1
# checks if n/x is smaller than
# the max gcd possible and n/x
# is greater than the resultant
# gcd till now, then r=x
elif n / x <= b and n / x > r :
r = n / x
# x = x + 1
x = x + 1
# traverses and prints d, 2d, 3d,
# ..., (k-1)·d,
i = 1
while i < k :
print (r * i, end = " ")
i = i + 1
last_term = n - (r * (k * (k - 1) / 2))
print (last_term)
# main driver
print_sequence(24,4)
print_sequence(24,5)
print_sequence(6,4)
# This code is contributed by Saloni Gupta
C#
// C# program to find the series with
// largest GCD and sum equals to n
using System;
class GFG {
// function to generate and
// print the sequence
static void print_sequence(int n, int k)
{
// stores the maximum gcd that can be
// possible of sequence.
int b = n / (k * (k + 1) / 2);
// if maximum gcd comes out to be
// zero then not possible
if (b == 0)
{
Console.Write("-1");
}
else
{
// the smallest gcd possible is 1
int r = 1;
// traverse the array to find out
// the max gcd possible
for (int x = 1; x * x <= n; x++)
{
// checks if the number is
// divisible or not
if (n % x != 0)
continue;
// checks if x is smaller than
// the max gcd possible and x
// is greater than the resultant
// gcd till now, then r=x
if (x <= b && x > r)
r = x;
// checks if n/x is smaller than
// the max gcd possible and n/x
// is greater than the resultant
// gcd till now, then r=x
if (n / x <= b && n / x > r)
r = n / x;
}
// traverses and prints d, 2d,
// 3d,..., (k-1)
for (int i = 1; i < k; i++)
Console.Write(r * i + " ");
// computes the last element of
// the sequence n-s.
int res = n - (r * (k *
(k - 1) / 2));
// prints the last element
Console.WriteLine(res);
}
}
// Driver Code
public static void Main()
{
int n = 24;
int k = 4;
print_sequence(n, k);
n = 24; k = 5;
print_sequence(n, k);
n = 6; k = 4;
print_sequence(n, k);
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to find the
// series with largest GCD
// and sum equals to n
// function to generate and
// print the sequence
function print_sequence($n, $k)
{
// stores the maximum gcd that
// can be possible of sequence.
$b = (int)($n / ($k * ($k + 1) / 2));
// if maximum gcd comes out to be
// zero then not possible
if ($b == 0)
{
echo(-1);
}
else
{
// the smallest gcd possible is 1
$r = 1;
// traverse the array to find out
// the max gcd possible
for ($x = 1; $x * $x <= $n; $x++)
{
// checks if the number is
// divisible or not
if ($n % $x != 0)
continue;
// checks if x is smaller than
// the max gcd possible and x
// is greater than the resultant
// gcd till now, then r=x
if ($x <= $b && $x > $r)
$r = $x;
// checks if n/x is smaller than
// the max gcd possible and n/x
// is greater than the resultant
// gcd till now, then r=x
if ($n / $x <= $b && $n / $x > $r)
$r = $n / $x;
}
// traverses and prints d, 2d, 3d,
// ..., (k-1)·d,
for ($i = 1; $i < $k; $i++)
echo($r * $i . " ");
// computes the last element of
// the sequence n-s.
$res = $n - ($r * ($k * ($k - 1) / 2));
// prints the last element
echo($res . "\n");
}
}
// Driver Code
$n = 24;
$k = 4;
print_sequence($n, $k);
$n = 24; $k = 5;
print_sequence($n, $k);
$n = 6; $k = 4;
print_sequence($n, $k);
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find the
// series with largest GCD
// and sum equals to n
// function to generate and
// print the sequence
function print_sequence(n, k)
{
// stores the maximum gcd that
// can be possible of sequence.
let b = parseInt(n / (k * (k + 1) / 2));
// if maximum gcd comes out to be
// zero then not possible
if (b == 0)
{
document.write(-1);
}
else
{
// the smallest gcd possible is 1
let r = 1;
// traverse the array to find out
// the max gcd possible
for (let x = 1; x * x <= n; x++)
{
// checks if the number is
// divisible or not
if (n % x != 0)
continue;
// checks if x is smaller than
// the max gcd possible and x
// is greater than the resultant
// gcd till now, then r=x
if (x <= b && x > r)
r = x;
// checks if n/x is smaller than
// the max gcd possible and n/x
// is greater than the resultant
// gcd till now, then r=x
if (n / x <= b && n / x > r)
r = n / x;
}
// traverses and prints d, 2d, 3d,
// ..., (k-1)·d,
for (let i = 1; i < k; i++)
document.write(r * i + " ");
// computes the last element of
// the sequence n-s.
let res = n - (r * (k * (k - 1) / 2));
// prints the last element
document.write(res + "<br>");
}
}
// Driver Code
let n = 24;
let k = 4;
print_sequence(n, k);
n = 24;
k = 5;
print_sequence(n, k);
n = 6;
k = 4;
print_sequence(n, k);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción :
2 4 6 12 1 2 3 4 14 -1
Complejidad de tiempo: O( sqrt (n) )
Espacio auxiliar: O(1)
Este artículo es una contribución de Raja Vikramaditya . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA