GCD最大且和等于n的级数-yiteyi-C++库

给定一个整数n，打印m个递增的数字，使m个数字的和等于n，并且 GCD 在所有可能的序列中，m个数的最大值。如果没有系列，则打印“-1”。 例如：

null

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 maximumpossible.              Input  : n = 6          m = 4 Output : -1 Explanation: It is not possible as the least GCD sequence will be 1+2+3+4 whichis greater then n, hence print -1.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 最常见的观察结果是，序列的gcd始终是n的除数。最大gcd可能是( 说b )将是n/sum，其中sum是1+2+的和。。M 如果b变成0，那么1+2+3之和+k超过n是无效的，因此输出“-1”。遍历以找出所有可能的除数，循环直到sqrt（n）。如果当前除数是I，则采取级数的最好的方法是考虑I、2 *I、3 *I、…（M-1）*I，它们的和等于 i*（m*（m-1））/2 .最后一个号码是n-s。 i是除数，n/i是另一个除数，所以也要检查一下。取可能除数的最大值( 说r )哪个应该小于或等于 B 并将序列打印为 r、 2*r，…（m-1）*r，n-s。 如果没有找到这样的除数，只需输出“-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 then                       
                                                 // the max gcd possible and x                       
                                                 // is greater then 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 then 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 then                       
                                                 // the max gcd possible and x                       
                                                 // is greater then 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 then 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 then                       
                                                 # the max gcd possible and x                       
                                                 # is greater then 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 then 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 then                       
                                                 // the max gcd possible and x                       
                                                 // is greater then 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 then 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 then                       
                                                 // the max gcd possible and x                       
                                                 // is greater then 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 then 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                                     .                                     ""                                     );                       
                                                 }                       
                         }                       
           
                         // 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 then                       
                                                 // the max gcd possible and x                       
                                                 // is greater then 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 then 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>                       

输出：

2 4 6 121 2 3 4 14-1

时间复杂性： O（sqrt（n）） 辅助空间： O（1）本文由 拉贾·维克拉马蒂亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章